Mercurial > hg > truffle
comparison graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java @ 2509:16b9a8b5ad39
Renamings Runtime=>GraalRuntime and Compiler=>GraalCompiler
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:50:44 +0200 |
parents | graal/Compiler/src/com/sun/c1x/alloc/LinearScan.java@9ec15d6914ca |
children | 4fdef1464592 |
comparison
equal
deleted
inserted
replaced
2508:fea94949e0a2 | 2509:16b9a8b5ad39 |
---|---|
1 /* | |
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. | |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
4 * | |
5 * This code is free software; you can redistribute it and/or modify it | |
6 * under the terms of the GNU General Public License version 2 only, as | |
7 * published by the Free Software Foundation. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
20 * or visit www.oracle.com if you need additional information or have any | |
21 * questions. | |
22 */ | |
23 package com.sun.c1x.alloc; | |
24 | |
25 import static com.sun.cri.ci.CiUtil.*; | |
26 import static java.lang.reflect.Modifier.*; | |
27 | |
28 import java.util.*; | |
29 | |
30 import com.sun.c1x.*; | |
31 import com.sun.c1x.alloc.Interval.*; | |
32 import com.sun.c1x.debug.*; | |
33 import com.sun.c1x.gen.*; | |
34 import com.sun.c1x.graph.*; | |
35 import com.sun.c1x.ir.*; | |
36 import com.sun.c1x.ir.BlockBegin.BlockFlag; | |
37 import com.sun.c1x.lir.*; | |
38 import com.sun.c1x.lir.LIRInstruction.OperandMode; | |
39 import com.sun.c1x.observer.*; | |
40 import com.sun.c1x.util.*; | |
41 import com.sun.c1x.value.*; | |
42 import com.sun.c1x.value.FrameState.PhiProcedure; | |
43 import com.sun.c1x.value.FrameState.ValueProcedure; | |
44 import com.sun.cri.ci.*; | |
45 import com.sun.cri.ri.*; | |
46 | |
47 /** | |
48 * An implementation of the linear scan register allocator algorithm described | |
49 * in <a href="http://doi.acm.org/10.1145/1064979.1064998">"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> | |
50 * by Christian Wimmer and Hanspeter Moessenboeck. | |
51 * | |
52 * @author Christian Wimmer (original HotSpot implementation) | |
53 * @author Thomas Wuerthinger | |
54 * @author Doug Simon | |
55 */ | |
56 public final class LinearScan { | |
57 | |
58 final C1XCompilation compilation; | |
59 final IR ir; | |
60 final LIRGenerator gen; | |
61 final FrameMap frameMap; | |
62 final RiRegisterAttributes[] registerAttributes; | |
63 final CiRegister[] registers; | |
64 | |
65 private static final int INITIAL_SPLIT_INTERVALS_CAPACITY = 32; | |
66 | |
67 /** | |
68 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. | |
69 */ | |
70 final BlockBegin[] sortedBlocks; | |
71 | |
72 final OperandPool operands; | |
73 | |
74 /** | |
75 * Number of stack slots used for intervals allocated to memory. | |
76 */ | |
77 int maxSpills; | |
78 | |
79 /** | |
80 * Unused spill slot for a single-word value because of alignment of a double-word value. | |
81 */ | |
82 CiStackSlot unusedSpillSlot; | |
83 | |
84 /** | |
85 * Map from {@linkplain #operandNumber(CiValue) operand numbers} to intervals. | |
86 */ | |
87 Interval[] intervals; | |
88 | |
89 /** | |
90 * The number of valid entries in {@link #intervals}. | |
91 */ | |
92 int intervalsSize; | |
93 | |
94 /** | |
95 * The index of the first entry in {@link #intervals} for a {@linkplain #createDerivedInterval(Interval) derived interval}. | |
96 */ | |
97 int firstDerivedIntervalIndex = -1; | |
98 | |
99 /** | |
100 * Intervals sorted by {@link Interval#from()}. | |
101 */ | |
102 Interval[] sortedIntervals; | |
103 | |
104 /** | |
105 * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. | |
106 * Entries should be retrieved with {@link #instructionForId(int)} as the id is | |
107 * not simply an index into this array. | |
108 */ | |
109 LIRInstruction[] opIdToInstructionMap; | |
110 | |
111 /** | |
112 * Map from an instruction {@linkplain LIRInstruction#id id} to the {@linkplain | |
113 * BlockBegin block} containing the instruction. Entries should be retrieved with | |
114 * {@link #blockForId(int)} as the id is not simply an index into this array. | |
115 */ | |
116 BlockBegin[] opIdToBlockMap; | |
117 | |
118 /** | |
119 * Bit set for each variable that is contained in each loop. | |
120 */ | |
121 BitMap2D intervalInLoop; | |
122 | |
123 public LinearScan(C1XCompilation compilation, IR ir, LIRGenerator gen, FrameMap frameMap) { | |
124 this.compilation = compilation; | |
125 this.ir = ir; | |
126 this.gen = gen; | |
127 this.frameMap = frameMap; | |
128 this.maxSpills = frameMap.initialSpillSlot(); | |
129 this.unusedSpillSlot = null; | |
130 this.sortedBlocks = ir.linearScanOrder().toArray(new BlockBegin[ir.linearScanOrder().size()]); | |
131 CiRegister[] allocatableRegisters = compilation.registerConfig.getAllocatableRegisters(); | |
132 this.registers = new CiRegister[CiRegister.maxRegisterNumber(allocatableRegisters) + 1]; | |
133 for (CiRegister reg : allocatableRegisters) { | |
134 registers[reg.number] = reg; | |
135 } | |
136 this.registerAttributes = compilation.registerConfig.getAttributesMap(); | |
137 this.operands = gen.operands; | |
138 } | |
139 | |
140 /** | |
141 * Converts an operand (variable or register) to an index in a flat address space covering all the | |
142 * {@linkplain CiVariable variables} and {@linkplain CiRegisterValue registers} being processed by this | |
143 * allocator. | |
144 */ | |
145 int operandNumber(CiValue operand) { | |
146 return operands.operandNumber(operand); | |
147 } | |
148 | |
149 static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() { | |
150 @Override | |
151 public boolean apply(Interval i) { | |
152 return i.operand.isRegister(); | |
153 } | |
154 }; | |
155 | |
156 static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() { | |
157 @Override | |
158 public boolean apply(Interval i) { | |
159 return i.operand.isVariable(); | |
160 } | |
161 }; | |
162 | |
163 static final IntervalPredicate IS_OOP_INTERVAL = new IntervalPredicate() { | |
164 @Override | |
165 public boolean apply(Interval i) { | |
166 return !i.operand.isRegister() && i.kind() == CiKind.Object; | |
167 } | |
168 }; | |
169 | |
170 /** | |
171 * Gets an object describing the attributes of a given register according to this register configuration. | |
172 */ | |
173 RiRegisterAttributes attributes(CiRegister reg) { | |
174 return registerAttributes[reg.number]; | |
175 } | |
176 | |
177 /** | |
178 * Allocates the next available spill slot for a value of a given kind. | |
179 */ | |
180 CiStackSlot allocateSpillSlot(CiKind kind) { | |
181 CiStackSlot spillSlot; | |
182 if (numberOfSpillSlots(kind) == 2) { | |
183 if (isOdd(maxSpills)) { | |
184 // alignment of double-slot values | |
185 // the hole because of the alignment is filled with the next single-slot value | |
186 assert unusedSpillSlot == null : "wasting a spill slot"; | |
187 unusedSpillSlot = CiStackSlot.get(kind, maxSpills); | |
188 maxSpills++; | |
189 } | |
190 spillSlot = CiStackSlot.get(kind, maxSpills); | |
191 maxSpills += 2; | |
192 } else if (unusedSpillSlot != null) { | |
193 // re-use hole that was the result of a previous double-word alignment | |
194 spillSlot = unusedSpillSlot; | |
195 unusedSpillSlot = null; | |
196 } else { | |
197 spillSlot = CiStackSlot.get(kind, maxSpills); | |
198 maxSpills++; | |
199 } | |
200 | |
201 return spillSlot; | |
202 } | |
203 | |
204 void assignSpillSlot(Interval interval) { | |
205 // assign the canonical spill slot of the parent (if a part of the interval | |
206 // is already spilled) or allocate a new spill slot | |
207 if (interval.spillSlot() != null) { | |
208 interval.assignLocation(interval.spillSlot()); | |
209 } else { | |
210 CiStackSlot slot = allocateSpillSlot(interval.kind()); | |
211 interval.setSpillSlot(slot); | |
212 interval.assignLocation(slot); | |
213 } | |
214 } | |
215 | |
216 /** | |
217 * Creates a new interval. | |
218 * | |
219 * @param operand the operand for the interval | |
220 * @return the created interval | |
221 */ | |
222 Interval createInterval(CiValue operand) { | |
223 assert isProcessed(operand); | |
224 assert operand.isLegal(); | |
225 int operandNumber = operandNumber(operand); | |
226 Interval interval = new Interval(operand, operandNumber); | |
227 assert operandNumber < intervalsSize; | |
228 assert intervals[operandNumber] == null; | |
229 intervals[operandNumber] = interval; | |
230 return interval; | |
231 } | |
232 | |
233 /** | |
234 * Creates an interval as a result of splitting or spilling another interval. | |
235 * | |
236 * @param source an interval being split of spilled | |
237 * @return a new interval derived from {@code source} | |
238 */ | |
239 Interval createDerivedInterval(Interval source) { | |
240 if (firstDerivedIntervalIndex == -1) { | |
241 firstDerivedIntervalIndex = intervalsSize; | |
242 } | |
243 if (intervalsSize == intervals.length) { | |
244 intervals = Arrays.copyOf(intervals, intervals.length * 2); | |
245 } | |
246 intervalsSize++; | |
247 Interval interval = createInterval(operands.newVariable(source.kind())); | |
248 assert intervals[intervalsSize - 1] == interval; | |
249 return interval; | |
250 } | |
251 | |
252 // copy the variable flags if an interval is split | |
253 void copyRegisterFlags(Interval from, Interval to) { | |
254 if (operands.mustBeByteRegister(from.operand)) { | |
255 operands.setMustBeByteRegister((CiVariable) to.operand); | |
256 } | |
257 | |
258 // Note: do not copy the mustStartInMemory flag because it is not necessary for child | |
259 // intervals (only the very beginning of the interval must be in memory) | |
260 } | |
261 | |
262 // access to block list (sorted in linear scan order) | |
263 int blockCount() { | |
264 assert sortedBlocks.length == ir.linearScanOrder().size() : "invalid cached block list"; | |
265 return sortedBlocks.length; | |
266 } | |
267 | |
268 BlockBegin blockAt(int index) { | |
269 assert sortedBlocks[index] == ir.linearScanOrder().get(index) : "invalid cached block list"; | |
270 return sortedBlocks[index]; | |
271 } | |
272 | |
273 /** | |
274 * Gets the size of the {@link LIRBlock#liveIn} and {@link LIRBlock#liveOut} sets for a basic block. These sets do | |
275 * not include any operands allocated as a result of creating {@linkplain #createDerivedInterval(Interval) derived | |
276 * intervals}. | |
277 */ | |
278 int liveSetSize() { | |
279 return firstDerivedIntervalIndex == -1 ? operands.size() : firstDerivedIntervalIndex; | |
280 } | |
281 | |
282 int numLoops() { | |
283 return ir.numLoops(); | |
284 } | |
285 | |
286 boolean isIntervalInLoop(int interval, int loop) { | |
287 return intervalInLoop.at(interval, loop); | |
288 } | |
289 | |
290 Interval intervalFor(CiValue operand) { | |
291 int operandNumber = operandNumber(operand); | |
292 assert operandNumber < intervalsSize; | |
293 return intervals[operandNumber]; | |
294 } | |
295 | |
296 /** | |
297 * Gets the highest instruction id allocated by this object. | |
298 */ | |
299 int maxOpId() { | |
300 assert opIdToInstructionMap.length > 0 : "no operations"; | |
301 return (opIdToInstructionMap.length - 1) << 1; | |
302 } | |
303 | |
304 /** | |
305 * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. | |
306 * All LIR instructions in a method have an index one greater than their linear-scan order predecesor | |
307 * with the first instruction having an index of 0. | |
308 */ | |
309 static int opIdToIndex(int opId) { | |
310 return opId >> 1; | |
311 } | |
312 | |
313 /** | |
314 * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}. | |
315 * | |
316 * @param opId an instruction {@linkplain LIRInstruction#id id} | |
317 * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id} | |
318 */ | |
319 LIRInstruction instructionForId(int opId) { | |
320 assert isEven(opId) : "opId not even"; | |
321 LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)]; | |
322 assert instr.id == opId; | |
323 return instr; | |
324 } | |
325 | |
326 /** | |
327 * Gets the block containing a given instruction. | |
328 * | |
329 * @param opId an instruction {@linkplain LIRInstruction#id id} | |
330 * @return the block containing the instruction denoted by {@code opId} | |
331 */ | |
332 BlockBegin blockForId(int opId) { | |
333 assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range"; | |
334 return opIdToBlockMap[opIdToIndex(opId)]; | |
335 } | |
336 | |
337 boolean isBlockBegin(int opId) { | |
338 return opId == 0 || blockForId(opId) != blockForId(opId - 1); | |
339 } | |
340 | |
341 boolean coversBlockBegin(int opId1, int opId2) { | |
342 return blockForId(opId1) != blockForId(opId2); | |
343 } | |
344 | |
345 /** | |
346 * Determines if an {@link LIRInstruction} destroys all caller saved registers. | |
347 * | |
348 * @param opId an instruction {@linkplain LIRInstruction#id id} | |
349 * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved registers. | |
350 */ | |
351 boolean hasCall(int opId) { | |
352 assert isEven(opId) : "opId not even"; | |
353 return instructionForId(opId).hasCall; | |
354 } | |
355 | |
356 /** | |
357 * Eliminates moves from register to stack if the stack slot is known to be correct. | |
358 */ | |
359 void changeSpillDefinitionPos(Interval interval, int defPos) { | |
360 assert interval.isSplitParent() : "can only be called for split parents"; | |
361 | |
362 switch (interval.spillState()) { | |
363 case NoDefinitionFound: | |
364 assert interval.spillDefinitionPos() == -1 : "must no be set before"; | |
365 interval.setSpillDefinitionPos(defPos); | |
366 interval.setSpillState(SpillState.NoSpillStore); | |
367 break; | |
368 | |
369 case NoSpillStore: | |
370 assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; | |
371 if (defPos < interval.spillDefinitionPos() - 2 || instructionForId(interval.spillDefinitionPos()).code == LIROpcode.Xir) { | |
372 // second definition found, so no spill optimization possible for this interval | |
373 interval.setSpillState(SpillState.NoOptimization); | |
374 } else { | |
375 // two consecutive definitions (because of two-operand LIR form) | |
376 assert blockForId(defPos) == blockForId(interval.spillDefinitionPos()) : "block must be equal"; | |
377 } | |
378 break; | |
379 | |
380 case NoOptimization: | |
381 // nothing to do | |
382 break; | |
383 | |
384 default: | |
385 throw new CiBailout("other states not allowed at this time"); | |
386 } | |
387 } | |
388 | |
389 // called during register allocation | |
390 void changeSpillState(Interval interval, int spillPos) { | |
391 switch (interval.spillState()) { | |
392 case NoSpillStore: { | |
393 int defLoopDepth = blockForId(interval.spillDefinitionPos()).loopDepth(); | |
394 int spillLoopDepth = blockForId(spillPos).loopDepth(); | |
395 | |
396 if (defLoopDepth < spillLoopDepth) { | |
397 // the loop depth of the spilling position is higher then the loop depth | |
398 // at the definition of the interval . move write to memory out of loop | |
399 // by storing at definitin of the interval | |
400 interval.setSpillState(SpillState.StoreAtDefinition); | |
401 } else { | |
402 // the interval is currently spilled only once, so for now there is no | |
403 // reason to store the interval at the definition | |
404 interval.setSpillState(SpillState.OneSpillStore); | |
405 } | |
406 break; | |
407 } | |
408 | |
409 case OneSpillStore: { | |
410 // the interval is spilled more then once, so it is better to store it to | |
411 // memory at the definition | |
412 interval.setSpillState(SpillState.StoreAtDefinition); | |
413 break; | |
414 } | |
415 | |
416 case StoreAtDefinition: | |
417 case StartInMemory: | |
418 case NoOptimization: | |
419 case NoDefinitionFound: | |
420 // nothing to do | |
421 break; | |
422 | |
423 default: | |
424 throw new CiBailout("other states not allowed at this time"); | |
425 } | |
426 } | |
427 | |
428 abstract static class IntervalPredicate { | |
429 abstract boolean apply(Interval i); | |
430 } | |
431 | |
432 private static final IntervalPredicate mustStoreAtDefinition = new IntervalPredicate() { | |
433 @Override | |
434 public boolean apply(Interval i) { | |
435 return i.isSplitParent() && i.spillState() == SpillState.StoreAtDefinition; | |
436 } | |
437 }; | |
438 | |
439 // called once before assignment of register numbers | |
440 void eliminateSpillMoves() { | |
441 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
442 TTY.println(" Eliminating unnecessary spill moves"); | |
443 } | |
444 | |
445 // collect all intervals that must be stored after their definition. | |
446 // the list is sorted by Interval.spillDefinitionPos | |
447 Interval interval; | |
448 interval = createUnhandledLists(mustStoreAtDefinition, null).first; | |
449 if (C1XOptions.DetailedAsserts) { | |
450 checkIntervals(interval); | |
451 } | |
452 | |
453 LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer(); | |
454 int numBlocks = blockCount(); | |
455 for (int i = 0; i < numBlocks; i++) { | |
456 BlockBegin block = blockAt(i); | |
457 List<LIRInstruction> instructions = block.lir().instructionsList(); | |
458 int numInst = instructions.size(); | |
459 boolean hasNew = false; | |
460 | |
461 // iterate all instructions of the block. skip the first because it is always a label | |
462 for (int j = 1; j < numInst; j++) { | |
463 LIRInstruction op = instructions.get(j); | |
464 int opId = op.id; | |
465 | |
466 if (opId == -1) { | |
467 CiValue resultOperand = op.result(); | |
468 // remove move from register to stack if the stack slot is guaranteed to be correct. | |
469 // only moves that have been inserted by LinearScan can be removed. | |
470 assert op.code == LIROpcode.Move : "only moves can have a opId of -1"; | |
471 assert resultOperand.isVariable() : "LinearScan inserts only moves to variables"; | |
472 | |
473 LIROp1 op1 = (LIROp1) op; | |
474 Interval curInterval = intervalFor(resultOperand); | |
475 | |
476 if (!curInterval.location().isRegister() && curInterval.alwaysInMemory()) { | |
477 // move target is a stack slot that is always correct, so eliminate instruction | |
478 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
479 TTY.println("eliminating move from interval %d to %d", operandNumber(op1.operand()), operandNumber(op1.result())); | |
480 } | |
481 instructions.set(j, null); // null-instructions are deleted by assignRegNum | |
482 } | |
483 | |
484 } else { | |
485 // insert move from register to stack just after the beginning of the interval | |
486 assert interval == Interval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order"; | |
487 assert interval == Interval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval"; | |
488 | |
489 while (interval != Interval.EndMarker && interval.spillDefinitionPos() == opId) { | |
490 if (!hasNew) { | |
491 // prepare insertion buffer (appended when all instructions of the block are processed) | |
492 insertionBuffer.init(block.lir()); | |
493 hasNew = true; | |
494 } | |
495 | |
496 CiValue fromLocation = interval.location(); | |
497 CiValue toLocation = canonicalSpillOpr(interval); | |
498 | |
499 assert fromLocation.isRegister() : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" + interval.spillState(); | |
500 assert toLocation.isStackSlot() : "to operand must be a stack slot"; | |
501 | |
502 insertionBuffer.move(j, fromLocation, toLocation, null); | |
503 | |
504 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
505 CiStackSlot slot = interval.spillSlot(); | |
506 TTY.println("inserting move after definition of interval %d to stack slot %d%s at opId %d", | |
507 interval.operandNumber, slot.index(), slot.inCallerFrame() ? " in caller frame" : "", opId); | |
508 } | |
509 | |
510 interval = interval.next; | |
511 } | |
512 } | |
513 } // end of instruction iteration | |
514 | |
515 if (hasNew) { | |
516 block.lir().append(insertionBuffer); | |
517 } | |
518 } // end of block iteration | |
519 | |
520 assert interval == Interval.EndMarker : "missed an interval"; | |
521 } | |
522 | |
523 private void checkIntervals(Interval interval) { | |
524 Interval prev = null; | |
525 Interval temp = interval; | |
526 while (temp != Interval.EndMarker) { | |
527 assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos"; | |
528 if (prev != null) { | |
529 assert temp.from() >= prev.from() : "intervals not sorted"; | |
530 assert temp.spillDefinitionPos() >= prev.spillDefinitionPos() : "when intervals are sorted by from : then they must also be sorted by spillDefinitionPos"; | |
531 } | |
532 | |
533 assert temp.spillSlot() != null : "interval has no spill slot assigned"; | |
534 assert temp.spillDefinitionPos() >= temp.from() : "invalid order"; | |
535 assert temp.spillDefinitionPos() <= temp.from() + 2 : "only intervals defined once at their start-pos can be optimized"; | |
536 | |
537 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
538 TTY.println("interval %d (from %d to %d) must be stored at %d", temp.operandNumber, temp.from(), temp.to(), temp.spillDefinitionPos()); | |
539 } | |
540 | |
541 prev = temp; | |
542 temp = temp.next; | |
543 } | |
544 } | |
545 | |
546 /** | |
547 * Numbers all instructions in all blocks. The numbering follows the {@linkplain ComputeLinearScanOrder linear scan order}. | |
548 */ | |
549 void numberInstructions() { | |
550 // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node. | |
551 int numBlocks = blockCount(); | |
552 int numInstructions = 0; | |
553 for (int i = 0; i < numBlocks; i++) { | |
554 numInstructions += blockAt(i).lir().instructionsList().size(); | |
555 } | |
556 | |
557 // initialize with correct length | |
558 opIdToInstructionMap = new LIRInstruction[numInstructions]; | |
559 opIdToBlockMap = new BlockBegin[numInstructions]; | |
560 | |
561 int opId = 0; | |
562 int index = 0; | |
563 | |
564 for (int i = 0; i < numBlocks; i++) { | |
565 BlockBegin block = blockAt(i); | |
566 block.setFirstLirInstructionId(opId); | |
567 List<LIRInstruction> instructions = block.lir().instructionsList(); | |
568 | |
569 int numInst = instructions.size(); | |
570 for (int j = 0; j < numInst; j++) { | |
571 LIRInstruction op = instructions.get(j); | |
572 op.id = opId; | |
573 | |
574 opIdToInstructionMap[index] = op; | |
575 opIdToBlockMap[index] = block; | |
576 assert instructionForId(opId) == op : "must match"; | |
577 | |
578 index++; | |
579 opId += 2; // numbering of lirOps by two | |
580 } | |
581 block.setLastLirInstructionId(opId - 2); | |
582 } | |
583 assert index == numInstructions : "must match"; | |
584 assert (index << 1) == opId : "must match: " + (index << 1); | |
585 } | |
586 | |
587 /** | |
588 * Computes local live sets (i.e. {@link LIRBlock#liveGen} and {@link LIRBlock#liveKill}) separately for each block. | |
589 */ | |
590 void computeLocalLiveSets() { | |
591 int numBlocks = blockCount(); | |
592 int liveSize = liveSetSize(); | |
593 | |
594 BitMap2D localIntervalInLoop = new BitMap2D(operands.size(), numLoops()); | |
595 | |
596 // iterate all blocks | |
597 for (int i = 0; i < numBlocks; i++) { | |
598 BlockBegin block = blockAt(i); | |
599 final CiBitMap liveGen = new CiBitMap(liveSize); | |
600 final CiBitMap liveKill = new CiBitMap(liveSize); | |
601 | |
602 if (block.isExceptionEntry()) { | |
603 // Phi functions at the begin of an exception handler are | |
604 // implicitly defined (= killed) at the beginning of the block. | |
605 block.stateBefore().forEachLivePhi(block, new PhiProcedure() { | |
606 public boolean doPhi(Phi phi) { | |
607 liveKill.set(operandNumber(phi.operand())); | |
608 return true; | |
609 } | |
610 }); | |
611 } | |
612 | |
613 List<LIRInstruction> instructions = block.lir().instructionsList(); | |
614 int numInst = instructions.size(); | |
615 | |
616 // iterate all instructions of the block. skip the first because it is always a label | |
617 assert !instructions.get(0).hasOperands() : "first operation must always be a label"; | |
618 for (int j = 1; j < numInst; j++) { | |
619 final LIRInstruction op = instructions.get(j); | |
620 | |
621 // iterate input operands of instruction | |
622 int n = op.operandCount(LIRInstruction.OperandMode.Input); | |
623 for (int k = 0; k < n; k++) { | |
624 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Input, k); | |
625 | |
626 if (operand.isVariable()) { | |
627 int operandNum = operandNumber(operand); | |
628 if (!liveKill.get(operandNum)) { | |
629 liveGen.set(operandNum); | |
630 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
631 TTY.println(" Setting liveGen for operand %d at instruction %d", operandNum, op.id); | |
632 } | |
633 } | |
634 if (block.loopIndex() >= 0) { | |
635 localIntervalInLoop.setBit(operandNum, block.loopIndex()); | |
636 } | |
637 } | |
638 | |
639 if (C1XOptions.DetailedAsserts) { | |
640 assert operand.isVariableOrRegister() : "visitor should only return register operands"; | |
641 verifyInput(block, liveKill, operand); | |
642 } | |
643 } | |
644 | |
645 // Add uses of live locals from interpreter's point of view for proper debug information generation | |
646 LIRDebugInfo info = op.info; | |
647 if (info != null) { | |
648 info.state.forEachLiveStateValue(new ValueProcedure() { | |
649 public void doValue(Value value) { | |
650 CiValue operand = value.operand(); | |
651 if (operand.isVariable()) { | |
652 int operandNum = operandNumber(operand); | |
653 if (!liveKill.get(operandNum)) { | |
654 liveGen.set(operandNum); | |
655 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
656 TTY.println(" Setting liveGen for value %s, LIR opId %d, operand %d", Util.valueString(value), op.id, operandNum); | |
657 } | |
658 } | |
659 } else if (operand.isRegister()) { | |
660 assert !isProcessed(operand) && !operand.kind.isObject(); | |
661 } else { | |
662 assert operand.isConstant() || operand.isIllegal() : "invalid operand for deoptimization value: " + value; | |
663 } | |
664 } | |
665 }); | |
666 } | |
667 | |
668 // iterate temp operands of instruction | |
669 n = op.operandCount(LIRInstruction.OperandMode.Temp); | |
670 for (int k = 0; k < n; k++) { | |
671 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Temp, k); | |
672 | |
673 if (operand.isVariable()) { | |
674 int varNum = operandNumber(operand); | |
675 liveKill.set(varNum); | |
676 if (block.loopIndex() >= 0) { | |
677 localIntervalInLoop.setBit(varNum, block.loopIndex()); | |
678 } | |
679 } | |
680 | |
681 if (C1XOptions.DetailedAsserts) { | |
682 assert operand.isVariableOrRegister() : "visitor should only return register operands"; | |
683 verifyTemp(liveKill, operand); | |
684 } | |
685 } | |
686 | |
687 // iterate output operands of instruction | |
688 n = op.operandCount(LIRInstruction.OperandMode.Output); | |
689 for (int k = 0; k < n; k++) { | |
690 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Output, k); | |
691 | |
692 if (operand.isVariable()) { | |
693 int varNum = operandNumber(operand); | |
694 liveKill.set(varNum); | |
695 if (block.loopIndex() >= 0) { | |
696 localIntervalInLoop.setBit(varNum, block.loopIndex()); | |
697 } | |
698 } | |
699 | |
700 if (C1XOptions.DetailedAsserts) { | |
701 assert operand.isVariableOrRegister() : "visitor should only return register operands"; | |
702 // fixed intervals are never live at block boundaries, so | |
703 // they need not be processed in live sets | |
704 // process them only in debug mode so that this can be checked | |
705 verifyTemp(liveKill, operand); | |
706 } | |
707 } | |
708 } // end of instruction iteration | |
709 | |
710 LIRBlock lirBlock = block.lirBlock(); | |
711 lirBlock.liveGen = liveGen; | |
712 lirBlock.liveKill = liveKill; | |
713 lirBlock.liveIn = new CiBitMap(liveSize); | |
714 lirBlock.liveOut = new CiBitMap(liveSize); | |
715 | |
716 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
717 TTY.println("liveGen B%d %s", block.blockID, block.lirBlock.liveGen); | |
718 TTY.println("liveKill B%d %s", block.blockID, block.lirBlock.liveKill); | |
719 } | |
720 } // end of block iteration | |
721 | |
722 intervalInLoop = localIntervalInLoop; | |
723 } | |
724 | |
725 private void verifyTemp(CiBitMap liveKill, CiValue operand) { | |
726 // fixed intervals are never live at block boundaries, so | |
727 // they need not be processed in live sets | |
728 // process them only in debug mode so that this can be checked | |
729 if (!operand.isVariable()) { | |
730 if (isProcessed(operand)) { | |
731 liveKill.set(operandNumber(operand)); | |
732 } | |
733 } | |
734 } | |
735 | |
736 private void verifyInput(BlockBegin block, CiBitMap liveKill, CiValue operand) { | |
737 // fixed intervals are never live at block boundaries, so | |
738 // they need not be processed in live sets. | |
739 // this is checked by these assertions to be sure about it. | |
740 // the entry block may have incoming | |
741 // values in registers, which is ok. | |
742 if (!operand.isVariable() && block != ir.startBlock) { | |
743 if (isProcessed(operand)) { | |
744 assert liveKill.get(operandNumber(operand)) : "using fixed register that is not defined in this block"; | |
745 } | |
746 } | |
747 } | |
748 | |
749 /** | |
750 * Performs a backward dataflow analysis to compute global live sets (i.e. {@link LIRBlock#liveIn} and | |
751 * {@link LIRBlock#liveOut}) for each block. | |
752 */ | |
753 void computeGlobalLiveSets() { | |
754 int numBlocks = blockCount(); | |
755 boolean changeOccurred; | |
756 boolean changeOccurredInBlock; | |
757 int iterationCount = 0; | |
758 CiBitMap liveOut = new CiBitMap(liveSetSize()); // scratch set for calculations | |
759 | |
760 // Perform a backward dataflow analysis to compute liveOut and liveIn for each block. | |
761 // The loop is executed until a fixpoint is reached (no changes in an iteration) | |
762 // Exception handlers must be processed because not all live values are | |
763 // present in the state array, e.g. because of global value numbering | |
764 do { | |
765 changeOccurred = false; | |
766 | |
767 // iterate all blocks in reverse order | |
768 for (int i = numBlocks - 1; i >= 0; i--) { | |
769 BlockBegin block = blockAt(i); | |
770 LIRBlock lirBlock = block.lirBlock(); | |
771 | |
772 changeOccurredInBlock = false; | |
773 | |
774 // liveOut(block) is the union of liveIn(sux), for successors sux of block | |
775 int n = block.numberOfSux(); | |
776 int e = block.numberOfExceptionHandlers(); | |
777 if (n + e > 0) { | |
778 // block has successors | |
779 if (n > 0) { | |
780 liveOut.setFrom(block.suxAt(0).lirBlock.liveIn); | |
781 for (int j = 1; j < n; j++) { | |
782 liveOut.setUnion(block.suxAt(j).lirBlock.liveIn); | |
783 } | |
784 } else { | |
785 liveOut.clearAll(); | |
786 } | |
787 for (int j = 0; j < e; j++) { | |
788 liveOut.setUnion(block.exceptionHandlerAt(j).lirBlock.liveIn); | |
789 } | |
790 | |
791 if (!lirBlock.liveOut.isSame(liveOut)) { | |
792 // A change occurred. Swap the old and new live out sets to avoid copying. | |
793 CiBitMap temp = lirBlock.liveOut; | |
794 lirBlock.liveOut = liveOut; | |
795 liveOut = temp; | |
796 | |
797 changeOccurred = true; | |
798 changeOccurredInBlock = true; | |
799 } | |
800 } | |
801 | |
802 if (iterationCount == 0 || changeOccurredInBlock) { | |
803 // liveIn(block) is the union of liveGen(block) with (liveOut(block) & !liveKill(block)) | |
804 // note: liveIn has to be computed only in first iteration or if liveOut has changed! | |
805 CiBitMap liveIn = lirBlock.liveIn; | |
806 liveIn.setFrom(lirBlock.liveOut); | |
807 liveIn.setDifference(lirBlock.liveKill); | |
808 liveIn.setUnion(lirBlock.liveGen); | |
809 } | |
810 | |
811 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
812 traceLiveness(changeOccurredInBlock, iterationCount, block); | |
813 } | |
814 } | |
815 iterationCount++; | |
816 | |
817 if (changeOccurred && iterationCount > 50) { | |
818 throw new CiBailout("too many iterations in computeGlobalLiveSets"); | |
819 } | |
820 } while (changeOccurred); | |
821 | |
822 if (C1XOptions.DetailedAsserts) { | |
823 verifyLiveness(numBlocks); | |
824 } | |
825 | |
826 // check that the liveIn set of the first block is empty | |
827 CiBitMap liveInArgs = new CiBitMap(ir.startBlock.lirBlock.liveIn.size()); | |
828 if (!ir.startBlock.lirBlock.liveIn.isSame(liveInArgs)) { | |
829 if (C1XOptions.DetailedAsserts) { | |
830 reportFailure(numBlocks); | |
831 } | |
832 | |
833 // bailout of if this occurs in product mode. | |
834 throw new CiBailout("liveIn set of first block must be empty"); | |
835 } | |
836 } | |
837 | |
838 private void reportFailure(int numBlocks) { | |
839 TTY.println("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined)"); | |
840 TTY.print("affected registers:"); | |
841 TTY.println(ir.startBlock.lirBlock.liveIn.toString()); | |
842 | |
843 // print some additional information to simplify debugging | |
844 for (int operandNum = 0; operandNum < ir.startBlock.lirBlock.liveIn.size(); operandNum++) { | |
845 if (ir.startBlock.lirBlock.liveIn.get(operandNum)) { | |
846 CiValue operand = operands.operandFor(operandNum); | |
847 Value instr = operand.isVariable() ? gen.operands.instructionForResult(((CiVariable) operand)) : null; | |
848 TTY.println(" var %d (HIR instruction %s)", operandNum, instr == null ? " " : instr.toString()); | |
849 | |
850 for (int j = 0; j < numBlocks; j++) { | |
851 BlockBegin block = blockAt(j); | |
852 if (block.lirBlock.liveGen.get(operandNum)) { | |
853 TTY.println(" used in block B%d", block.blockID); | |
854 } | |
855 if (block.lirBlock.liveKill.get(operandNum)) { | |
856 TTY.println(" defined in block B%d", block.blockID); | |
857 } | |
858 } | |
859 } | |
860 } | |
861 } | |
862 | |
863 private void verifyLiveness(int numBlocks) { | |
864 // check that fixed intervals are not live at block boundaries | |
865 // (live set must be empty at fixed intervals) | |
866 for (int i = 0; i < numBlocks; i++) { | |
867 BlockBegin block = blockAt(i); | |
868 for (int j = 0; j <= operands.maxRegisterNumber(); j++) { | |
869 assert !block.lirBlock.liveIn.get(j) : "liveIn set of fixed register must be empty"; | |
870 assert !block.lirBlock.liveOut.get(j) : "liveOut set of fixed register must be empty"; | |
871 assert !block.lirBlock.liveGen.get(j) : "liveGen set of fixed register must be empty"; | |
872 } | |
873 } | |
874 } | |
875 | |
876 private void traceLiveness(boolean changeOccurredInBlock, int iterationCount, BlockBegin block) { | |
877 char c = iterationCount == 0 || changeOccurredInBlock ? '*' : ' '; | |
878 TTY.print("(%d) liveIn%c B%d ", iterationCount, c, block.blockID); | |
879 TTY.println(block.lirBlock.liveIn.toString()); | |
880 TTY.print("(%d) liveOut%c B%d ", iterationCount, c, block.blockID); | |
881 TTY.println(block.lirBlock.liveOut.toString()); | |
882 } | |
883 | |
884 Interval addUse(CiValue operand, int from, int to, RegisterPriority registerPriority, CiKind kind) { | |
885 if (!isProcessed(operand)) { | |
886 return null; | |
887 } | |
888 if (C1XOptions.TraceLinearScanLevel >= 2 && kind == null) { | |
889 TTY.println(" use %s from %d to %d (%s)", operand, from, to, registerPriority.name()); | |
890 } | |
891 | |
892 if (kind == null) { | |
893 kind = operand.kind.stackKind(); | |
894 } | |
895 Interval interval = intervalFor(operand); | |
896 if (interval == null) { | |
897 interval = createInterval(operand); | |
898 } | |
899 | |
900 if (kind != CiKind.Illegal) { | |
901 interval.setKind(kind); | |
902 } | |
903 | |
904 if (operand.isVariable() && gen.operands.mustStayInMemory((CiVariable) operand)) { | |
905 interval.addRange(from, maxOpId()); | |
906 } else { | |
907 interval.addRange(from, to); | |
908 } | |
909 | |
910 interval.addUsePos(to, registerPriority); | |
911 return interval; | |
912 } | |
913 | |
914 void addTemp(CiValue operand, int tempPos, RegisterPriority registerPriority, CiKind kind) { | |
915 if (!isProcessed(operand)) { | |
916 return; | |
917 } | |
918 Interval interval = intervalFor(operand); | |
919 if (interval == null) { | |
920 interval = createInterval(operand); | |
921 } | |
922 | |
923 if (kind != CiKind.Illegal) { | |
924 interval.setKind(kind); | |
925 } | |
926 | |
927 interval.addRange(tempPos, tempPos + 1); | |
928 interval.addUsePos(tempPos, registerPriority); | |
929 } | |
930 | |
931 boolean isProcessed(CiValue operand) { | |
932 return !operand.isRegister() || attributes(operand.asRegister()).isAllocatable; | |
933 } | |
934 | |
935 void addDef(CiValue operand, int defPos, RegisterPriority registerPriority, CiKind kind) { | |
936 if (!isProcessed(operand)) { | |
937 return; | |
938 } | |
939 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
940 TTY.println(" def %s defPos %d (%s)", operand, defPos, registerPriority.name()); | |
941 } | |
942 Interval interval = intervalFor(operand); | |
943 if (interval != null) { | |
944 | |
945 if (kind != CiKind.Illegal) { | |
946 interval.setKind(kind); | |
947 } | |
948 | |
949 Range r = interval.first(); | |
950 if (r.from <= defPos) { | |
951 // Update the starting point (when a range is first created for a use, its | |
952 // start is the beginning of the current block until a def is encountered.) | |
953 r.from = defPos; | |
954 interval.addUsePos(defPos, registerPriority); | |
955 | |
956 } else { | |
957 // Dead value - make vacuous interval | |
958 // also add register priority for dead intervals | |
959 interval.addRange(defPos, defPos + 1); | |
960 interval.addUsePos(defPos, registerPriority); | |
961 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
962 TTY.println("Warning: def of operand %s at %d occurs without use", operand, defPos); | |
963 } | |
964 } | |
965 | |
966 } else { | |
967 // Dead value - make vacuous interval | |
968 // also add register priority for dead intervals | |
969 interval = createInterval(operand); | |
970 if (kind != CiKind.Illegal) { | |
971 interval.setKind(kind); | |
972 } | |
973 | |
974 interval.addRange(defPos, defPos + 1); | |
975 interval.addUsePos(defPos, registerPriority); | |
976 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
977 TTY.println("Warning: dead value %s at %d in live intervals", operand, defPos); | |
978 } | |
979 } | |
980 | |
981 changeSpillDefinitionPos(interval, defPos); | |
982 if (registerPriority == RegisterPriority.None && interval.spillState().ordinal() <= SpillState.StartInMemory.ordinal()) { | |
983 // detection of method-parameters and roundfp-results | |
984 // TODO: move this directly to position where use-kind is computed | |
985 interval.setSpillState(SpillState.StartInMemory); | |
986 } | |
987 } | |
988 | |
989 /** | |
990 * Determines the register priority for an instruction's output/result operand. | |
991 */ | |
992 RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op, CiValue operand) { | |
993 if (op.code == LIROpcode.Move) { | |
994 LIROp1 move = (LIROp1) op; | |
995 CiValue res = move.result(); | |
996 boolean resultInMemory = res.isVariable() && operands.mustStartInMemory((CiVariable) res); | |
997 | |
998 if (resultInMemory) { | |
999 // Begin of an interval with mustStartInMemory set. | |
1000 // This interval will always get a stack slot first, so return noUse. | |
1001 return RegisterPriority.None; | |
1002 | |
1003 } else if (move.operand().isStackSlot()) { | |
1004 // method argument (condition must be equal to handleMethodArguments) | |
1005 return RegisterPriority.None; | |
1006 | |
1007 } else if (move.operand().isVariableOrRegister() && move.result().isVariableOrRegister()) { | |
1008 // Move from register to register | |
1009 if (blockForId(op.id).checkBlockFlag(BlockBegin.BlockFlag.OsrEntry)) { | |
1010 // special handling of phi-function moves inside osr-entry blocks | |
1011 // input operand must have a register instead of output operand (leads to better register | |
1012 // allocation) | |
1013 return RegisterPriority.ShouldHaveRegister; | |
1014 } | |
1015 } | |
1016 } | |
1017 | |
1018 if (operand.isVariable() && operands.mustStartInMemory((CiVariable) operand)) { | |
1019 // result is a stack-slot, so prevent immediate reloading | |
1020 return RegisterPriority.None; | |
1021 } | |
1022 | |
1023 // all other operands require a register | |
1024 return RegisterPriority.MustHaveRegister; | |
1025 } | |
1026 | |
1027 /** | |
1028 * Determines the priority which with an instruction's input operand will be allocated a register. | |
1029 */ | |
1030 RegisterPriority registerPriorityOfInputOperand(LIRInstruction op, CiValue operand) { | |
1031 if (op.code == LIROpcode.Move) { | |
1032 LIROp1 move = (LIROp1) op; | |
1033 CiValue res = move.result(); | |
1034 boolean resultInMemory = res.isVariable() && operands.mustStartInMemory((CiVariable) res); | |
1035 | |
1036 if (resultInMemory) { | |
1037 // Move to an interval with mustStartInMemory set. | |
1038 // To avoid moves from stack to stack (not allowed) force the input operand to a register | |
1039 return RegisterPriority.MustHaveRegister; | |
1040 | |
1041 } else if (move.operand().isVariableOrRegister() && move.result().isVariableOrRegister()) { | |
1042 // Move from register to register | |
1043 if (blockForId(op.id).checkBlockFlag(BlockBegin.BlockFlag.OsrEntry)) { | |
1044 // special handling of phi-function moves inside osr-entry blocks | |
1045 // input operand must have a register instead of output operand (leads to better register | |
1046 // allocation) | |
1047 return RegisterPriority.MustHaveRegister; | |
1048 } | |
1049 | |
1050 // The input operand is not forced to a register (moves from stack to register are allowed), | |
1051 // but it is faster if the input operand is in a register | |
1052 return RegisterPriority.ShouldHaveRegister; | |
1053 } | |
1054 } | |
1055 | |
1056 if (compilation.target.arch.isX86()) { | |
1057 if (op.code == LIROpcode.Cmove) { | |
1058 // conditional moves can handle stack operands | |
1059 assert op.result().isVariableOrRegister(); | |
1060 return RegisterPriority.ShouldHaveRegister; | |
1061 } | |
1062 | |
1063 // optimizations for second input operand of arithmetic operations on Intel | |
1064 // this operand is allowed to be on the stack in some cases | |
1065 CiKind kind = operand.kind.stackKind(); | |
1066 if (kind == CiKind.Float || kind == CiKind.Double) { | |
1067 // SSE float instruction (CiKind.Double only supported with SSE2) | |
1068 switch (op.code) { | |
1069 case Cmp: | |
1070 case Add: | |
1071 case Sub: | |
1072 case Mul: | |
1073 case Div: { | |
1074 LIROp2 op2 = (LIROp2) op; | |
1075 if (op2.operand1() != op2.operand2() && op2.operand2() == operand) { | |
1076 assert (op2.result().isVariableOrRegister() || op.code == LIROpcode.Cmp) && op2.operand1().isVariableOrRegister() : "cannot mark second operand as stack if others are not in register"; | |
1077 return RegisterPriority.ShouldHaveRegister; | |
1078 } | |
1079 } | |
1080 } | |
1081 } else if (kind != CiKind.Long) { | |
1082 // integer instruction (note: long operands must always be in register) | |
1083 switch (op.code) { | |
1084 case Cmp: | |
1085 case Add: | |
1086 case Sub: | |
1087 case LogicAnd: | |
1088 case LogicOr: | |
1089 case LogicXor: { | |
1090 LIROp2 op2 = (LIROp2) op; | |
1091 if (op2.operand1() != op2.operand2() && op2.operand2() == operand) { | |
1092 assert (op2.result().isVariableOrRegister() || op.code == LIROpcode.Cmp) && op2.operand1().isVariableOrRegister() : "cannot mark second operand as stack if others are not in register"; | |
1093 return RegisterPriority.ShouldHaveRegister; | |
1094 } | |
1095 } | |
1096 } | |
1097 } | |
1098 } // X86 | |
1099 | |
1100 // all other operands require a register | |
1101 return RegisterPriority.MustHaveRegister; | |
1102 } | |
1103 | |
1104 /** | |
1105 * Optimizes moves related to incoming stack based arguments. | |
1106 * The interval for the destination of such moves is assigned | |
1107 * the stack slot (which is in the caller's frame) as its | |
1108 * spill slot. | |
1109 */ | |
1110 void handleMethodArguments(LIRInstruction op) { | |
1111 if (op.code == LIROpcode.Move) { | |
1112 LIROp1 move = (LIROp1) op; | |
1113 | |
1114 if (move.operand().isStackSlot()) { | |
1115 CiStackSlot slot = (CiStackSlot) move.operand(); | |
1116 if (C1XOptions.DetailedAsserts) { | |
1117 int argSlots = compilation.method.signature().argumentSlots(!isStatic(compilation.method.accessFlags())); | |
1118 assert slot.index() >= 0 && slot.index() < argSlots; | |
1119 assert move.id > 0 : "invalid id"; | |
1120 assert blockForId(move.id).numberOfPreds() == 0 : "move from stack must be in first block"; | |
1121 assert move.result().isVariable() : "result of move must be a variable"; | |
1122 | |
1123 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
1124 TTY.println("found move from stack slot %s to %s", slot, move.result()); | |
1125 } | |
1126 } | |
1127 | |
1128 Interval interval = intervalFor(move.result()); | |
1129 CiStackSlot copySlot = slot; | |
1130 if (C1XOptions.CopyPointerStackArguments && slot.kind == CiKind.Object) { | |
1131 copySlot = allocateSpillSlot(slot.kind); | |
1132 } | |
1133 interval.setSpillSlot(copySlot); | |
1134 interval.assignLocation(copySlot); | |
1135 } | |
1136 } | |
1137 } | |
1138 | |
1139 void addRegisterHints(LIRInstruction op) { | |
1140 switch (op.code) { | |
1141 case Move: // fall through | |
1142 case Convert: { | |
1143 LIROp1 move = (LIROp1) op; | |
1144 | |
1145 CiValue moveFrom = move.operand(); | |
1146 CiValue moveTo = move.result(); | |
1147 | |
1148 if (moveTo.isVariableOrRegister() && moveFrom.isVariableOrRegister()) { | |
1149 Interval from = intervalFor(moveFrom); | |
1150 Interval to = intervalFor(moveTo); | |
1151 if (from != null && to != null) { | |
1152 to.setLocationHint(from); | |
1153 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
1154 TTY.println("operation at opId %d: added hint from interval %d to %d", move.id, from.operandNumber, to.operandNumber); | |
1155 } | |
1156 } | |
1157 } | |
1158 break; | |
1159 } | |
1160 case Cmove: { | |
1161 LIROp2 cmove = (LIROp2) op; | |
1162 | |
1163 CiValue moveFrom = cmove.operand1(); | |
1164 CiValue moveTo = cmove.result(); | |
1165 | |
1166 if (moveTo.isVariableOrRegister() && moveFrom.isVariableOrRegister()) { | |
1167 Interval from = intervalFor(moveFrom); | |
1168 Interval to = intervalFor(moveTo); | |
1169 if (from != null && to != null) { | |
1170 to.setLocationHint(from); | |
1171 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
1172 TTY.println("operation at opId %d: added hint from interval %d to %d", cmove.id, from.operandNumber, to.operandNumber); | |
1173 } | |
1174 } | |
1175 } | |
1176 break; | |
1177 } | |
1178 } | |
1179 } | |
1180 | |
1181 void buildIntervals() { | |
1182 intervalsSize = operands.size(); | |
1183 intervals = new Interval[intervalsSize + INITIAL_SPLIT_INTERVALS_CAPACITY]; | |
1184 | |
1185 // create a list with all caller-save registers (cpu, fpu, xmm) | |
1186 RiRegisterConfig registerConfig = compilation.registerConfig; | |
1187 CiRegister[] callerSaveRegs = registerConfig.getCallerSaveRegisters(); | |
1188 | |
1189 // iterate all blocks in reverse order | |
1190 for (int i = blockCount() - 1; i >= 0; i--) { | |
1191 BlockBegin block = blockAt(i); | |
1192 List<LIRInstruction> instructions = block.lir().instructionsList(); | |
1193 final int blockFrom = block.firstLirInstructionId(); | |
1194 int blockTo = block.lastLirInstructionId(); | |
1195 | |
1196 assert blockFrom == instructions.get(0).id; | |
1197 assert blockTo == instructions.get(instructions.size() - 1).id; | |
1198 | |
1199 // Update intervals for operands live at the end of this block; | |
1200 CiBitMap live = block.lirBlock.liveOut; | |
1201 for (int operandNum = live.nextSetBit(0); operandNum >= 0; operandNum = live.nextSetBit(operandNum + 1)) { | |
1202 assert live.get(operandNum) : "should not stop here otherwise"; | |
1203 CiValue operand = operands.operandFor(operandNum); | |
1204 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
1205 TTY.println("live in %s to %d", operand, blockTo + 2); | |
1206 } | |
1207 | |
1208 addUse(operand, blockFrom, blockTo + 2, RegisterPriority.None, CiKind.Illegal); | |
1209 | |
1210 // add special use positions for loop-end blocks when the | |
1211 // interval is used anywhere inside this loop. It's possible | |
1212 // that the block was part of a non-natural loop, so it might | |
1213 // have an invalid loop index. | |
1214 if (block.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) && block.loopIndex() != -1 && isIntervalInLoop(operandNum, block.loopIndex())) { | |
1215 intervalFor(operand).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd); | |
1216 } | |
1217 } | |
1218 | |
1219 // iterate all instructions of the block in reverse order. | |
1220 // skip the first instruction because it is always a label | |
1221 // definitions of intervals are processed before uses | |
1222 assert !instructions.get(0).hasOperands() : "first operation must always be a label"; | |
1223 for (int j = instructions.size() - 1; j >= 1; j--) { | |
1224 LIRInstruction op = instructions.get(j); | |
1225 final int opId = op.id; | |
1226 | |
1227 // add a temp range for each register if operation destroys caller-save registers | |
1228 if (op.hasCall) { | |
1229 for (CiRegister r : callerSaveRegs) { | |
1230 if (attributes(r).isAllocatable) { | |
1231 addTemp(r.asValue(), opId, RegisterPriority.None, CiKind.Illegal); | |
1232 } | |
1233 } | |
1234 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
1235 TTY.println("operation destroys all caller-save registers"); | |
1236 } | |
1237 } | |
1238 | |
1239 // Add any platform dependent temps | |
1240 pdAddTemps(op); | |
1241 | |
1242 // visit definitions (output and temp operands) | |
1243 int k; | |
1244 int n; | |
1245 n = op.operandCount(LIRInstruction.OperandMode.Output); | |
1246 for (k = 0; k < n; k++) { | |
1247 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Output, k); | |
1248 assert operand.isVariableOrRegister(); | |
1249 addDef(operand, opId, registerPriorityOfOutputOperand(op, operand), operand.kind.stackKind()); | |
1250 } | |
1251 | |
1252 n = op.operandCount(LIRInstruction.OperandMode.Temp); | |
1253 for (k = 0; k < n; k++) { | |
1254 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Temp, k); | |
1255 assert operand.isVariableOrRegister(); | |
1256 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
1257 TTY.println(" temp %s tempPos %d (%s)", operand, opId, RegisterPriority.MustHaveRegister.name()); | |
1258 } | |
1259 addTemp(operand, opId, RegisterPriority.MustHaveRegister, operand.kind.stackKind()); | |
1260 } | |
1261 | |
1262 // visit uses (input operands) | |
1263 n = op.operandCount(LIRInstruction.OperandMode.Input); | |
1264 for (k = 0; k < n; k++) { | |
1265 CiValue operand = op.operandAt(LIRInstruction.OperandMode.Input, k); | |
1266 assert operand.isVariableOrRegister(); | |
1267 RegisterPriority p = registerPriorityOfInputOperand(op, operand); | |
1268 Interval interval = addUse(operand, blockFrom, opId, p, null); | |
1269 if (interval != null && op instanceof LIRXirInstruction) { | |
1270 Range range = interval.first(); | |
1271 // (tw) Increase range by 1 in order to overlap the input with the temp and the output operand. | |
1272 if (range.to == opId) { | |
1273 range.to++; | |
1274 } | |
1275 } | |
1276 } | |
1277 | |
1278 // Add uses of live locals from interpreter's point of view for proper | |
1279 // debug information generation | |
1280 // Treat these operands as temp values (if the live range is extended | |
1281 // to a call site, the value would be in a register at the call otherwise) | |
1282 LIRDebugInfo info = op.info; | |
1283 if (info != null) { | |
1284 info.state.forEachLiveStateValue(new ValueProcedure() { | |
1285 public void doValue(Value value) { | |
1286 CiValue operand = value.operand(); | |
1287 if (operand.isVariableOrRegister()) { | |
1288 addUse(operand, blockFrom, (opId + 1), RegisterPriority.None, null); | |
1289 } | |
1290 } | |
1291 }); | |
1292 } | |
1293 | |
1294 // special steps for some instructions (especially moves) | |
1295 handleMethodArguments(op); | |
1296 addRegisterHints(op); | |
1297 | |
1298 } // end of instruction iteration | |
1299 | |
1300 // (tw) Make sure that no spill store optimization is applied for phi instructions that flow into exception handlers. | |
1301 if (block.isExceptionEntry()) { | |
1302 FrameState stateBefore = block.stateBefore(); | |
1303 stateBefore.forEachLivePhi(block, new PhiProcedure() { | |
1304 @Override | |
1305 public boolean doPhi(Phi phi) { | |
1306 Interval interval = intervalFor(phi.operand()); | |
1307 if (interval != null) { | |
1308 interval.setSpillState(SpillState.NoOptimization); | |
1309 } | |
1310 return true; | |
1311 } | |
1312 }); | |
1313 } | |
1314 | |
1315 } // end of block iteration | |
1316 | |
1317 // add the range [0, 1] to all fixed intervals. | |
1318 // the register allocator need not handle unhandled fixed intervals | |
1319 for (Interval interval : intervals) { | |
1320 if (interval != null && interval.operand.isRegister()) { | |
1321 interval.addRange(0, 1); | |
1322 } | |
1323 } | |
1324 } | |
1325 | |
1326 // * Phase 5: actual register allocation | |
1327 | |
1328 private void pdAddTemps(LIRInstruction op) { | |
1329 // TODO Platform dependent! | |
1330 assert compilation.target.arch.isX86(); | |
1331 | |
1332 switch (op.code) { | |
1333 case Tan: | |
1334 case Sin: | |
1335 case Cos: { | |
1336 // The slow path for these functions may need to save and | |
1337 // restore all live registers but we don't want to save and | |
1338 // restore everything all the time, so mark the xmms as being | |
1339 // killed. If the slow path were explicit or we could propagate | |
1340 // live register masks down to the assembly we could do better | |
1341 // but we don't have any easy way to do that right now. We | |
1342 // could also consider not killing all xmm registers if we | |
1343 // assume that slow paths are uncommon but it's not clear that | |
1344 // would be a good idea. | |
1345 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
1346 TTY.println("killing XMMs for trig"); | |
1347 } | |
1348 int opId = op.id; | |
1349 | |
1350 for (CiRegister r : compilation.registerConfig.getCallerSaveRegisters()) { | |
1351 if (r.isFpu()) { | |
1352 addTemp(r.asValue(), opId, RegisterPriority.None, CiKind.Illegal); | |
1353 } | |
1354 } | |
1355 break; | |
1356 } | |
1357 } | |
1358 | |
1359 } | |
1360 | |
1361 boolean isSorted(Interval[] intervals) { | |
1362 int from = -1; | |
1363 for (Interval interval : intervals) { | |
1364 assert interval != null; | |
1365 assert from <= interval.from(); | |
1366 from = interval.from(); | |
1367 | |
1368 // XXX: very slow! | |
1369 assert Arrays.asList(this.intervals).contains(interval); | |
1370 } | |
1371 return true; | |
1372 } | |
1373 | |
1374 Interval addToList(Interval first, Interval prev, Interval interval) { | |
1375 Interval newFirst = first; | |
1376 if (prev != null) { | |
1377 prev.next = interval; | |
1378 } else { | |
1379 newFirst = interval; | |
1380 } | |
1381 return newFirst; | |
1382 } | |
1383 | |
1384 Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) { | |
1385 assert isSorted(sortedIntervals) : "interval list is not sorted"; | |
1386 | |
1387 Interval list1 = Interval.EndMarker; | |
1388 Interval list2 = Interval.EndMarker; | |
1389 | |
1390 Interval list1Prev = null; | |
1391 Interval list2Prev = null; | |
1392 Interval v; | |
1393 | |
1394 int n = sortedIntervals.length; | |
1395 for (int i = 0; i < n; i++) { | |
1396 v = sortedIntervals[i]; | |
1397 if (v == null) { | |
1398 continue; | |
1399 } | |
1400 | |
1401 if (isList1.apply(v)) { | |
1402 list1 = addToList(list1, list1Prev, v); | |
1403 list1Prev = v; | |
1404 } else if (isList2 == null || isList2.apply(v)) { | |
1405 list2 = addToList(list2, list2Prev, v); | |
1406 list2Prev = v; | |
1407 } | |
1408 } | |
1409 | |
1410 if (list1Prev != null) { | |
1411 list1Prev.next = Interval.EndMarker; | |
1412 } | |
1413 if (list2Prev != null) { | |
1414 list2Prev.next = Interval.EndMarker; | |
1415 } | |
1416 | |
1417 assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel"; | |
1418 assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel"; | |
1419 | |
1420 return new Interval.Pair(list1, list2); | |
1421 } | |
1422 | |
1423 void sortIntervalsBeforeAllocation() { | |
1424 int sortedLen = 0; | |
1425 for (Interval interval : intervals) { | |
1426 if (interval != null) { | |
1427 sortedLen++; | |
1428 } | |
1429 } | |
1430 | |
1431 Interval[] sortedList = new Interval[sortedLen]; | |
1432 int sortedIdx = 0; | |
1433 int sortedFromMax = -1; | |
1434 | |
1435 // special sorting algorithm: the original interval-list is almost sorted, | |
1436 // only some intervals are swapped. So this is much faster than a complete QuickSort | |
1437 for (Interval interval : intervals) { | |
1438 if (interval != null) { | |
1439 int from = interval.from(); | |
1440 | |
1441 if (sortedFromMax <= from) { | |
1442 sortedList[sortedIdx++] = interval; | |
1443 sortedFromMax = interval.from(); | |
1444 } else { | |
1445 // the assumption that the intervals are already sorted failed, | |
1446 // so this interval must be sorted in manually | |
1447 int j; | |
1448 for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) { | |
1449 sortedList[j + 1] = sortedList[j]; | |
1450 } | |
1451 sortedList[j + 1] = interval; | |
1452 sortedIdx++; | |
1453 } | |
1454 } | |
1455 } | |
1456 sortedIntervals = sortedList; | |
1457 } | |
1458 | |
1459 void sortIntervalsAfterAllocation() { | |
1460 if (firstDerivedIntervalIndex == -1) { | |
1461 // no intervals have been added during allocation, so sorted list is already up to date | |
1462 return; | |
1463 } | |
1464 | |
1465 Interval[] oldList = sortedIntervals; | |
1466 Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize); | |
1467 int oldLen = oldList.length; | |
1468 int newLen = newList.length; | |
1469 | |
1470 // conventional sort-algorithm for new intervals | |
1471 Arrays.sort(newList, INTERVAL_COMPARATOR); | |
1472 | |
1473 // merge old and new list (both already sorted) into one combined list | |
1474 Interval[] combinedList = new Interval[oldLen + newLen]; | |
1475 int oldIdx = 0; | |
1476 int newIdx = 0; | |
1477 | |
1478 while (oldIdx + newIdx < combinedList.length) { | |
1479 if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) { | |
1480 combinedList[oldIdx + newIdx] = oldList[oldIdx]; | |
1481 oldIdx++; | |
1482 } else { | |
1483 combinedList[oldIdx + newIdx] = newList[newIdx]; | |
1484 newIdx++; | |
1485 } | |
1486 } | |
1487 | |
1488 sortedIntervals = combinedList; | |
1489 } | |
1490 | |
1491 private static final Comparator<Interval> INTERVAL_COMPARATOR = new Comparator<Interval>() { | |
1492 | |
1493 public int compare(Interval a, Interval b) { | |
1494 if (a != null) { | |
1495 if (b != null) { | |
1496 return a.from() - b.from(); | |
1497 } else { | |
1498 return -1; | |
1499 } | |
1500 } else { | |
1501 if (b != null) { | |
1502 return 1; | |
1503 } else { | |
1504 return 0; | |
1505 } | |
1506 } | |
1507 } | |
1508 }; | |
1509 | |
1510 public void allocateRegisters() { | |
1511 Interval precoloredIntervals; | |
1512 Interval notPrecoloredIntervals; | |
1513 | |
1514 Interval.Pair result = createUnhandledLists(IS_PRECOLORED_INTERVAL, IS_VARIABLE_INTERVAL); | |
1515 precoloredIntervals = result.first; | |
1516 notPrecoloredIntervals = result.second; | |
1517 | |
1518 // allocate cpu registers | |
1519 LinearScanWalker lsw = new LinearScanWalker(this, precoloredIntervals, notPrecoloredIntervals); | |
1520 lsw.walk(); | |
1521 lsw.finishAllocation(); | |
1522 } | |
1523 | |
1524 // * Phase 6: resolve data flow | |
1525 // (insert moves at edges between blocks if intervals have been split) | |
1526 | |
1527 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode | |
1528 // instead of returning null | |
1529 Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { | |
1530 Interval result = interval.getSplitChildAtOpId(opId, mode, this); | |
1531 | |
1532 if (result != null) { | |
1533 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
1534 TTY.println("Split child at pos " + opId + " of interval " + interval.toString() + " is " + result.toString()); | |
1535 } | |
1536 return result; | |
1537 } | |
1538 | |
1539 throw new CiBailout("LinearScan: interval is null"); | |
1540 } | |
1541 | |
1542 Interval intervalAtBlockBegin(BlockBegin block, CiValue operand) { | |
1543 assert operand.isVariable() : "register number out of bounds"; | |
1544 assert intervalFor(operand) != null : "no interval found"; | |
1545 | |
1546 return splitChildAtOpId(intervalFor(operand), block.firstLirInstructionId(), LIRInstruction.OperandMode.Output); | |
1547 } | |
1548 | |
1549 Interval intervalAtBlockEnd(BlockBegin block, CiValue operand) { | |
1550 assert operand.isVariable() : "register number out of bounds"; | |
1551 assert intervalFor(operand) != null : "no interval found"; | |
1552 | |
1553 return splitChildAtOpId(intervalFor(operand), block.lastLirInstructionId() + 1, LIRInstruction.OperandMode.Output); | |
1554 } | |
1555 | |
1556 Interval intervalAtOpId(CiValue operand, int opId) { | |
1557 assert operand.isVariable() : "register number out of bounds"; | |
1558 assert intervalFor(operand) != null : "no interval found"; | |
1559 | |
1560 return splitChildAtOpId(intervalFor(operand), opId, LIRInstruction.OperandMode.Input); | |
1561 } | |
1562 | |
1563 void resolveCollectMappings(BlockBegin fromBlock, BlockBegin toBlock, MoveResolver moveResolver) { | |
1564 assert moveResolver.checkEmpty(); | |
1565 | |
1566 int numOperands = operands.size(); | |
1567 CiBitMap liveAtEdge = toBlock.lirBlock.liveIn; | |
1568 | |
1569 // visit all variables for which the liveAtEdge bit is set | |
1570 for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { | |
1571 assert operandNum < numOperands : "live information set for not exisiting interval"; | |
1572 assert fromBlock.lirBlock.liveOut.get(operandNum) && toBlock.lirBlock.liveIn.get(operandNum) : "interval not live at this edge"; | |
1573 | |
1574 CiValue liveOperand = operands.operandFor(operandNum); | |
1575 Interval fromInterval = intervalAtBlockEnd(fromBlock, liveOperand); | |
1576 Interval toInterval = intervalAtBlockBegin(toBlock, liveOperand); | |
1577 | |
1578 if (fromInterval != toInterval && (fromInterval.location() != toInterval.location())) { | |
1579 // need to insert move instruction | |
1580 moveResolver.addMapping(fromInterval, toInterval); | |
1581 } | |
1582 } | |
1583 } | |
1584 | |
1585 void resolveFindInsertPos(BlockBegin fromBlock, BlockBegin toBlock, MoveResolver moveResolver) { | |
1586 if (fromBlock.numberOfSux() <= 1) { | |
1587 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
1588 TTY.println("inserting moves at end of fromBlock B%d", fromBlock.blockID); | |
1589 } | |
1590 | |
1591 List<LIRInstruction> instructions = fromBlock.lir().instructionsList(); | |
1592 LIRInstruction instr = instructions.get(instructions.size() - 1); | |
1593 if (instr instanceof LIRBranch) { | |
1594 LIRBranch branch = (LIRBranch) instr; | |
1595 // insert moves before branch | |
1596 assert branch.cond() == Condition.TRUE : "block does not end with an unconditional jump"; | |
1597 moveResolver.setInsertPosition(fromBlock.lir(), instructions.size() - 2); | |
1598 } else { | |
1599 moveResolver.setInsertPosition(fromBlock.lir(), instructions.size() - 1); | |
1600 } | |
1601 | |
1602 } else { | |
1603 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
1604 TTY.println("inserting moves at beginning of toBlock B%d", toBlock.blockID); | |
1605 } | |
1606 | |
1607 if (C1XOptions.DetailedAsserts) { | |
1608 assert fromBlock.lir().instructionsList().get(0) instanceof LIRLabel : "block does not start with a label"; | |
1609 | |
1610 // because the number of predecessor edges matches the number of | |
1611 // successor edges, blocks which are reached by switch statements | |
1612 // may have be more than one predecessor but it will be guaranteed | |
1613 // that all predecessors will be the same. | |
1614 for (int i = 0; i < toBlock.numberOfPreds(); i++) { | |
1615 assert fromBlock == toBlock.predAt(i) : "all critical edges must be broken"; | |
1616 } | |
1617 } | |
1618 | |
1619 moveResolver.setInsertPosition(toBlock.lir(), 0); | |
1620 } | |
1621 } | |
1622 | |
1623 /** | |
1624 * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that | |
1625 * have been split. | |
1626 */ | |
1627 void resolveDataFlow() { | |
1628 int numBlocks = blockCount(); | |
1629 MoveResolver moveResolver = new MoveResolver(this); | |
1630 CiBitMap blockCompleted = new CiBitMap(numBlocks); | |
1631 CiBitMap alreadyResolved = new CiBitMap(numBlocks); | |
1632 | |
1633 int i; | |
1634 for (i = 0; i < numBlocks; i++) { | |
1635 BlockBegin block = blockAt(i); | |
1636 | |
1637 // check if block has only one predecessor and only one successor | |
1638 if (block.numberOfPreds() == 1 && block.numberOfSux() == 1 && block.numberOfExceptionHandlers() == 0 && !block.isExceptionEntry()) { | |
1639 List<LIRInstruction> instructions = block.lir().instructionsList(); | |
1640 assert instructions.get(0).code == LIROpcode.Label : "block must start with label"; | |
1641 assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successors must end with branch"; | |
1642 assert ((LIRBranch) instructions.get(instructions.size() - 1)).cond() == Condition.TRUE : "block with successor must end with unconditional branch"; | |
1643 | |
1644 // check if block is empty (only label and branch) | |
1645 if (instructions.size() == 2) { | |
1646 BlockBegin pred = block.predAt(0); | |
1647 BlockBegin sux = block.suxAt(0); | |
1648 | |
1649 // prevent optimization of two consecutive blocks | |
1650 if (!blockCompleted.get(pred.linearScanNumber()) && !blockCompleted.get(sux.linearScanNumber())) { | |
1651 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
1652 TTY.println(" optimizing empty block B%d (pred: B%d, sux: B%d)", block.blockID, pred.blockID, sux.blockID); | |
1653 } | |
1654 blockCompleted.set(block.linearScanNumber()); | |
1655 | |
1656 // directly resolve between pred and sux (without looking at the empty block between) | |
1657 resolveCollectMappings(pred, sux, moveResolver); | |
1658 if (moveResolver.hasMappings()) { | |
1659 moveResolver.setInsertPosition(block.lir(), 0); | |
1660 moveResolver.resolveAndAppendMoves(); | |
1661 } | |
1662 } | |
1663 } | |
1664 } | |
1665 } | |
1666 | |
1667 for (i = 0; i < numBlocks; i++) { | |
1668 if (!blockCompleted.get(i)) { | |
1669 BlockBegin fromBlock = blockAt(i); | |
1670 alreadyResolved.setFrom(blockCompleted); | |
1671 | |
1672 int numSux = fromBlock.numberOfSux(); | |
1673 for (int s = 0; s < numSux; s++) { | |
1674 BlockBegin toBlock = fromBlock.suxAt(s); | |
1675 | |
1676 // check for duplicate edges between the same blocks (can happen with switch blocks) | |
1677 if (!alreadyResolved.get(toBlock.linearScanNumber())) { | |
1678 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
1679 TTY.println(" processing edge between B%d and B%d", fromBlock.blockID, toBlock.blockID); | |
1680 } | |
1681 alreadyResolved.set(toBlock.linearScanNumber()); | |
1682 | |
1683 // collect all intervals that have been split between fromBlock and toBlock | |
1684 resolveCollectMappings(fromBlock, toBlock, moveResolver); | |
1685 if (moveResolver.hasMappings()) { | |
1686 resolveFindInsertPos(fromBlock, toBlock, moveResolver); | |
1687 moveResolver.resolveAndAppendMoves(); | |
1688 } | |
1689 } | |
1690 } | |
1691 } | |
1692 } | |
1693 } | |
1694 | |
1695 void resolveExceptionEntry(BlockBegin block, CiValue operand, MoveResolver moveResolver) { | |
1696 if (intervalFor(operand) == null) { | |
1697 // if a phi function is never used, no interval is created . ignore this | |
1698 return; | |
1699 } | |
1700 | |
1701 Interval interval = intervalAtBlockBegin(block, operand); | |
1702 CiValue location = interval.location(); | |
1703 | |
1704 if (location.isRegister() && interval.alwaysInMemory()) { | |
1705 // the interval is split to get a short range that is located on the stack | |
1706 // in the following two cases: | |
1707 // * the interval started in memory (e.g. method parameter), but is currently in a register | |
1708 // this is an optimization for exception handling that reduces the number of moves that | |
1709 // are necessary for resolving the states when an exception uses this exception handler | |
1710 // * the interval would be on the fpu stack at the begin of the exception handler | |
1711 // this is not allowed because of the complicated fpu stack handling on Intel | |
1712 | |
1713 // range that will be spilled to memory | |
1714 int fromOpId = block.firstLirInstructionId(); | |
1715 int toOpId = fromOpId + 1; // short live range of length 1 | |
1716 assert interval.from() <= fromOpId && interval.to() >= toOpId : "no split allowed between exception entry and first instruction"; | |
1717 | |
1718 if (interval.from() != fromOpId) { | |
1719 // the part before fromOpId is unchanged | |
1720 interval = interval.split(fromOpId, this); | |
1721 interval.assignLocation(location); | |
1722 } | |
1723 assert interval.from() == fromOpId : "must be true now"; | |
1724 | |
1725 Interval spilledPart = interval; | |
1726 if (interval.to() != toOpId) { | |
1727 // the part after toOpId is unchanged | |
1728 spilledPart = interval.splitFromStart(toOpId, this); | |
1729 moveResolver.addMapping(spilledPart, interval); | |
1730 } | |
1731 assignSpillSlot(spilledPart); | |
1732 | |
1733 assert spilledPart.from() == fromOpId && spilledPart.to() == toOpId : "just checking"; | |
1734 } | |
1735 } | |
1736 | |
1737 void resolveExceptionEntry(final BlockBegin block, final MoveResolver moveResolver) { | |
1738 assert block.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry) : "should not call otherwise"; | |
1739 assert moveResolver.checkEmpty(); | |
1740 | |
1741 // visit all registers where the liveIn bit is set | |
1742 for (int operandNum = block.lirBlock.liveIn.nextSetBit(0); operandNum >= 0; operandNum = block.lirBlock.liveIn.nextSetBit(operandNum + 1)) { | |
1743 resolveExceptionEntry(block, operands.operandFor(operandNum), moveResolver); | |
1744 } | |
1745 | |
1746 // the liveIn bits are not set for phi functions of the xhandler entry, so iterate them separately | |
1747 block.stateBefore().forEachLivePhi(block, new PhiProcedure() { | |
1748 public boolean doPhi(Phi phi) { | |
1749 resolveExceptionEntry(block, phi.operand(), moveResolver); | |
1750 return true; | |
1751 } | |
1752 }); | |
1753 | |
1754 if (moveResolver.hasMappings()) { | |
1755 // insert moves after first instruction | |
1756 moveResolver.setInsertPosition(block.lir(), 0); | |
1757 moveResolver.resolveAndAppendMoves(); | |
1758 } | |
1759 } | |
1760 | |
1761 void resolveExceptionEdge(ExceptionHandler handler, int throwingOpId, CiValue operand, Phi phi, MoveResolver moveResolver) { | |
1762 if (intervalFor(operand) == null) { | |
1763 // if a phi function is never used, no interval is created . ignore this | |
1764 return; | |
1765 } | |
1766 | |
1767 // the computation of toInterval is equal to resolveCollectMappings, | |
1768 // but fromInterval is more complicated because of phi functions | |
1769 BlockBegin toBlock = handler.entryBlock(); | |
1770 Interval toInterval = intervalAtBlockBegin(toBlock, operand); | |
1771 | |
1772 if (phi != null) { | |
1773 // phi function of the exception entry block | |
1774 // no moves are created for this phi function in the LIRGenerator, so the | |
1775 // interval at the throwing instruction must be searched using the operands | |
1776 // of the phi function | |
1777 Value fromValue = phi.inputAt(handler.phiOperand()); | |
1778 Constant con = null; | |
1779 if (fromValue instanceof Constant) { | |
1780 con = (Constant) fromValue; | |
1781 } | |
1782 if (con != null && (con.operand().isIllegal() || con.operand().isConstant())) { | |
1783 // unpinned constants may have no register, so add mapping from constant to interval | |
1784 moveResolver.addMapping(con.asConstant(), toInterval); | |
1785 } else { | |
1786 // search split child at the throwing opId | |
1787 Interval fromInterval = intervalAtOpId(fromValue.operand(), throwingOpId); | |
1788 if (fromInterval != toInterval) { | |
1789 moveResolver.addMapping(fromInterval, toInterval); | |
1790 // with phi functions it can happen that the same fromValue is used in | |
1791 // multiple mappings, so notify move-resolver that this is allowed | |
1792 moveResolver.setMultipleReadsAllowed(); | |
1793 } | |
1794 } | |
1795 } else { | |
1796 // no phi function, so use regNum also for fromInterval | |
1797 // search split child at the throwing opId | |
1798 Interval fromInterval = intervalAtOpId(operand, throwingOpId); | |
1799 if (fromInterval != toInterval) { | |
1800 // optimization to reduce number of moves: when toInterval is on stack and | |
1801 // the stack slot is known to be always correct, then no move is necessary | |
1802 if (!fromInterval.alwaysInMemory() || fromInterval.spillSlot() != toInterval.location()) { | |
1803 moveResolver.addMapping(fromInterval, toInterval); | |
1804 } | |
1805 } | |
1806 } | |
1807 } | |
1808 | |
1809 void resolveExceptionEdge(final ExceptionHandler handler, final int throwingOpId, final MoveResolver moveResolver) { | |
1810 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
1811 TTY.println("resolving exception handler B%d: throwingOpId=%d", handler.entryBlock().blockID, throwingOpId); | |
1812 } | |
1813 | |
1814 assert moveResolver.checkEmpty(); | |
1815 assert handler.lirOpId() == -1 : "already processed this xhandler"; | |
1816 handler.setLirOpId(throwingOpId); | |
1817 assert handler.entryCode() == null : "code already present"; | |
1818 | |
1819 // visit all registers where the liveIn bit is set | |
1820 BlockBegin block = handler.entryBlock(); | |
1821 for (int operandNum = block.lirBlock.liveIn.nextSetBit(0); operandNum >= 0; operandNum = block.lirBlock.liveIn.nextSetBit(operandNum + 1)) { | |
1822 resolveExceptionEdge(handler, throwingOpId, operands.operandFor(operandNum), null, moveResolver); | |
1823 } | |
1824 | |
1825 // the liveIn bits are not set for phi functions of the xhandler entry, so iterate them separately | |
1826 block.stateBefore().forEachLivePhi(block, new PhiProcedure() { | |
1827 public boolean doPhi(Phi phi) { | |
1828 resolveExceptionEdge(handler, throwingOpId, phi.operand(), phi, moveResolver); | |
1829 return true; | |
1830 } | |
1831 }); | |
1832 | |
1833 if (moveResolver.hasMappings()) { | |
1834 LIRList entryCode = new LIRList(gen); | |
1835 moveResolver.setInsertPosition(entryCode, 0); | |
1836 moveResolver.resolveAndAppendMoves(); | |
1837 | |
1838 entryCode.jump(handler.entryBlock()); | |
1839 handler.setEntryCode(entryCode); | |
1840 } | |
1841 } | |
1842 | |
1843 void resolveExceptionHandlers() { | |
1844 MoveResolver moveResolver = new MoveResolver(this); | |
1845 //LIRVisitState visitor = new LIRVisitState(); | |
1846 int numBlocks = blockCount(); | |
1847 | |
1848 int i; | |
1849 for (i = 0; i < numBlocks; i++) { | |
1850 BlockBegin block = blockAt(i); | |
1851 if (block.checkBlockFlag(BlockFlag.ExceptionEntry)) { | |
1852 resolveExceptionEntry(block, moveResolver); | |
1853 } | |
1854 } | |
1855 | |
1856 for (i = 0; i < numBlocks; i++) { | |
1857 BlockBegin block = blockAt(i); | |
1858 LIRList ops = block.lir(); | |
1859 int numOps = ops.length(); | |
1860 | |
1861 // iterate all instructions of the block. skip the first because it is always a label | |
1862 assert !ops.at(0).hasOperands() : "first operation must always be a label"; | |
1863 for (int j = 1; j < numOps; j++) { | |
1864 LIRInstruction op = ops.at(j); | |
1865 int opId = op.id; | |
1866 | |
1867 if (opId != -1 && op.info != null) { | |
1868 // visit operation to collect all operands | |
1869 for (ExceptionHandler handler : op.exceptionEdges()) { | |
1870 resolveExceptionEdge(handler, opId, moveResolver); | |
1871 } | |
1872 | |
1873 } else if (C1XOptions.DetailedAsserts) { | |
1874 assert op.exceptionEdges().size() == 0 : "missed exception handler"; | |
1875 } | |
1876 } | |
1877 } | |
1878 } | |
1879 | |
1880 // * Phase 7: assign register numbers back to LIR | |
1881 // (includes computation of debug information and oop maps) | |
1882 | |
1883 boolean verifyAssignedLocation(Interval interval, CiValue location) { | |
1884 CiKind kind = interval.kind(); | |
1885 | |
1886 assert location.isRegister() || location.isStackSlot(); | |
1887 | |
1888 if (location.isRegister()) { | |
1889 CiRegister reg = location.asRegister(); | |
1890 | |
1891 // register | |
1892 switch (kind) { | |
1893 case Byte: | |
1894 case Char: | |
1895 case Short: | |
1896 case Jsr: | |
1897 case Word: | |
1898 case Object: | |
1899 case Int: { | |
1900 assert reg.isCpu() : "not cpu register"; | |
1901 break; | |
1902 } | |
1903 | |
1904 case Long: { | |
1905 assert reg.isCpu() : "not cpu register"; | |
1906 break; | |
1907 } | |
1908 | |
1909 case Float: { | |
1910 assert !compilation.target.arch.isX86() || reg.isFpu() : "not xmm register: " + reg; | |
1911 break; | |
1912 } | |
1913 | |
1914 case Double: { | |
1915 assert !compilation.target.arch.isX86() || reg.isFpu() : "not xmm register: " + reg; | |
1916 break; | |
1917 } | |
1918 | |
1919 default: { | |
1920 throw Util.shouldNotReachHere(); | |
1921 } | |
1922 } | |
1923 } | |
1924 return true; | |
1925 } | |
1926 | |
1927 CiStackSlot canonicalSpillOpr(Interval interval) { | |
1928 assert interval.spillSlot() != null : "canonical spill slot not set"; | |
1929 return interval.spillSlot(); | |
1930 } | |
1931 | |
1932 /** | |
1933 * Assigns the allocated location for an LIR instruction operand back into the instruction. | |
1934 * | |
1935 * @param operand an LIR instruction operand | |
1936 * @param opId the id of the LIR instruction using {@code operand} | |
1937 * @param mode the usage mode for {@code operand} by the instruction | |
1938 * @return the location assigned for the operand | |
1939 */ | |
1940 private CiValue colorLirOperand(CiVariable operand, int opId, OperandMode mode) { | |
1941 Interval interval = intervalFor(operand); | |
1942 assert interval != null : "interval must exist"; | |
1943 | |
1944 if (opId != -1) { | |
1945 if (C1XOptions.DetailedAsserts) { | |
1946 BlockBegin block = blockForId(opId); | |
1947 if (block.numberOfSux() <= 1 && opId == block.lastLirInstructionId()) { | |
1948 // check if spill moves could have been appended at the end of this block, but | |
1949 // before the branch instruction. So the split child information for this branch would | |
1950 // be incorrect. | |
1951 LIRInstruction instr = block.lir().instructionsList().get(block.lir().instructionsList().size() - 1); | |
1952 if (instr instanceof LIRBranch) { | |
1953 LIRBranch branch = (LIRBranch) instr; | |
1954 if (block.lirBlock.liveOut.get(operandNumber(operand))) { | |
1955 assert branch.cond() == Condition.TRUE : "block does not end with an unconditional jump"; | |
1956 throw new CiBailout("can't get split child for the last branch of a block because the information would be incorrect (moves are inserted before the branch in resolveDataFlow)"); | |
1957 } | |
1958 } | |
1959 } | |
1960 } | |
1961 | |
1962 // operands are not changed when an interval is split during allocation, | |
1963 // so search the right interval here | |
1964 interval = splitChildAtOpId(interval, opId, mode); | |
1965 } | |
1966 | |
1967 return interval.location(); | |
1968 } | |
1969 | |
1970 IntervalWalker initComputeOopMaps() { | |
1971 // setup lists of potential oops for walking | |
1972 Interval oopIntervals; | |
1973 Interval nonOopIntervals; | |
1974 | |
1975 oopIntervals = createUnhandledLists(IS_OOP_INTERVAL, null).first; | |
1976 | |
1977 // intervals that have no oops inside need not to be processed. | |
1978 // to ensure a walking until the last instruction id, add a dummy interval | |
1979 // with a high operation id | |
1980 nonOopIntervals = new Interval(CiValue.IllegalValue, -1); | |
1981 nonOopIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); | |
1982 | |
1983 return new IntervalWalker(this, oopIntervals, nonOopIntervals); | |
1984 } | |
1985 | |
1986 void computeOopMap(IntervalWalker iw, LIRInstruction op, LIRDebugInfo info, boolean isCallSite, CiBitMap frameRefMap, CiBitMap regRefMap) { | |
1987 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
1988 TTY.println("creating oop map at opId %d", op.id); | |
1989 } | |
1990 | |
1991 // walk before the current operation . intervals that start at | |
1992 // the operation (i.e. output operands of the operation) are not | |
1993 // included in the oop map | |
1994 iw.walkBefore(op.id); | |
1995 | |
1996 // Iterate through active intervals | |
1997 for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) { | |
1998 CiValue operand = interval.operand; | |
1999 | |
2000 assert interval.currentFrom() <= op.id && op.id <= interval.currentTo() : "interval should not be active otherwise"; | |
2001 assert interval.operand.isVariable() : "fixed interval found"; | |
2002 | |
2003 // Check if this range covers the instruction. Intervals that | |
2004 // start or end at the current operation are not included in the | |
2005 // oop map, except in the case of patching moves. For patching | |
2006 // moves, any intervals which end at this instruction are included | |
2007 // in the oop map since we may safepoint while doing the patch | |
2008 // before we've consumed the inputs. | |
2009 if (op.id < interval.currentTo()) { | |
2010 // caller-save registers must not be included into oop-maps at calls | |
2011 assert !isCallSite || !operand.isRegister() || !isCallerSave(operand) : "interval is in a caller-save register at a call . register will be overwritten"; | |
2012 | |
2013 CiValue location = interval.location(); | |
2014 if (location.isStackSlot()) { | |
2015 location = frameMap.toStackAddress((CiStackSlot) location); | |
2016 } | |
2017 info.setOop(location, compilation, frameRefMap, regRefMap); | |
2018 | |
2019 // Spill optimization: when the stack value is guaranteed to be always correct, | |
2020 // then it must be added to the oop map even if the interval is currently in a register | |
2021 if (interval.alwaysInMemory() && op.id > interval.spillDefinitionPos() && !interval.location().equals(interval.spillSlot())) { | |
2022 assert interval.spillDefinitionPos() > 0 : "position not set correctly"; | |
2023 assert interval.spillSlot() != null : "no spill slot assigned"; | |
2024 assert !interval.operand.isRegister() : "interval is on stack : so stack slot is registered twice"; | |
2025 info.setOop(frameMap.toStackAddress(interval.spillSlot()), compilation, frameRefMap, regRefMap); | |
2026 } | |
2027 } | |
2028 } | |
2029 } | |
2030 | |
2031 private boolean isCallerSave(CiValue operand) { | |
2032 return attributes(operand.asRegister()).isCallerSave; | |
2033 } | |
2034 | |
2035 void computeOopMap(IntervalWalker iw, LIRInstruction op, LIRDebugInfo info, CiBitMap frameRefMap, CiBitMap regRefMap) { | |
2036 computeOopMap(iw, op, info, op.hasCall, frameRefMap, regRefMap); | |
2037 if (op instanceof LIRCall) { | |
2038 List<CiValue> pointerSlots = ((LIRCall) op).pointerSlots; | |
2039 if (pointerSlots != null) { | |
2040 for (CiValue v : pointerSlots) { | |
2041 info.setOop(v, compilation, frameRefMap, regRefMap); | |
2042 } | |
2043 } | |
2044 } else if (op instanceof LIRXirInstruction) { | |
2045 List<CiValue> pointerSlots = ((LIRXirInstruction) op).pointerSlots; | |
2046 if (pointerSlots != null) { | |
2047 for (CiValue v : pointerSlots) { | |
2048 info.setOop(v, compilation, frameRefMap, regRefMap); | |
2049 } | |
2050 } | |
2051 } | |
2052 } | |
2053 | |
2054 CiValue toCiValue(int opId, Value value) { | |
2055 if (value != null && value.operand() != CiValue.IllegalValue) { | |
2056 CiValue operand = value.operand(); | |
2057 Constant con = null; | |
2058 if (value instanceof Constant) { | |
2059 con = (Constant) value; | |
2060 } | |
2061 | |
2062 assert con == null || operand.isVariable() || operand.isConstant() || operand.isIllegal() : "Constant instructions have only constant operands (or illegal if constant is optimized away)"; | |
2063 | |
2064 if (con != null && !con.isLive() && !operand.isConstant()) { | |
2065 // Unpinned constants may have a variable operand for a part of the lifetime | |
2066 // or may be illegal when it was optimized away, | |
2067 // so always use a constant operand | |
2068 operand = con.asConstant(); | |
2069 } | |
2070 | |
2071 if (operand.isVariable()) { | |
2072 OperandMode mode = OperandMode.Input; | |
2073 BlockBegin block = blockForId(opId); | |
2074 if (block.numberOfSux() == 1 && opId == block.lastLirInstructionId()) { | |
2075 // generating debug information for the last instruction of a block. | |
2076 // if this instruction is a branch, spill moves are inserted before this branch | |
2077 // and so the wrong operand would be returned (spill moves at block boundaries are not | |
2078 // considered in the live ranges of intervals) | |
2079 // Solution: use the first opId of the branch target block instead. | |
2080 final LIRInstruction instr = block.lir().instructionsList().get(block.lir().instructionsList().size() - 1); | |
2081 if (instr instanceof LIRBranch) { | |
2082 if (block.lirBlock.liveOut.get(operandNumber(operand))) { | |
2083 opId = block.suxAt(0).firstLirInstructionId(); | |
2084 mode = OperandMode.Output; | |
2085 } | |
2086 } | |
2087 } | |
2088 | |
2089 // Get current location of operand | |
2090 // The operand must be live because debug information is considered when building the intervals | |
2091 // if the interval is not live, colorLirOperand will cause an assert on failure | |
2092 operand = colorLirOperand((CiVariable) operand, opId, mode); | |
2093 assert !hasCall(opId) || operand.isStackSlot() || !isCallerSave(operand) : "cannot have caller-save register operands at calls"; | |
2094 return operand; | |
2095 } else if (operand.isRegister()) { | |
2096 assert value instanceof LoadRegister; | |
2097 return operand; | |
2098 } else { | |
2099 assert value instanceof Constant; | |
2100 assert operand.isConstant() : "operand must be constant"; | |
2101 return operand; | |
2102 } | |
2103 } else { | |
2104 // return a dummy value because real value not needed | |
2105 return CiValue.IllegalValue; | |
2106 } | |
2107 } | |
2108 | |
2109 CiFrame computeFrameForState(int opId, FrameState state, CiBitMap frameRefMap) { | |
2110 CiFrame callerFrame = null; | |
2111 | |
2112 FrameState callerState = state.callerState(); | |
2113 if (callerState != null) { | |
2114 // process recursively to compute outermost scope first | |
2115 callerFrame = computeFrameForState(opId, callerState, frameRefMap); | |
2116 } | |
2117 | |
2118 CiValue[] values = new CiValue[state.valuesSize() + state.locksSize()]; | |
2119 int valueIndex = 0; | |
2120 | |
2121 for (int i = 0; i < state.valuesSize(); i++) { | |
2122 values[valueIndex++] = toCiValue(opId, state.valueAt(i)); | |
2123 } | |
2124 | |
2125 for (int i = 0; i < state.locksSize(); i++) { | |
2126 if (compilation.runtime.sizeOfBasicObjectLock() != 0) { | |
2127 CiStackSlot monitorAddress = frameMap.toMonitorBaseStackAddress(i); | |
2128 values[valueIndex++] = monitorAddress; | |
2129 assert frameRefMap != null; | |
2130 CiStackSlot objectAddress = frameMap.toMonitorObjectStackAddress(i); | |
2131 LIRDebugInfo.setBit(frameRefMap, objectAddress.index()); | |
2132 } else { | |
2133 Value lock = state.lockAt(i); | |
2134 if (lock.isConstant() && compilation.runtime.asJavaClass(lock.asConstant()) != null) { | |
2135 // lock on class for synchronized static method | |
2136 values[valueIndex++] = lock.asConstant(); | |
2137 } else { | |
2138 values[valueIndex++] = toCiValue(opId, lock); | |
2139 } | |
2140 } | |
2141 } | |
2142 | |
2143 return new CiFrame(callerFrame, state.scope().method, state.bci, values, state.localsSize(), state.stackSize(), state.locksSize()); | |
2144 } | |
2145 | |
2146 private void computeDebugInfo(IntervalWalker iw, LIRInstruction op) { | |
2147 assert iw != null : "interval walker needed for debug information"; | |
2148 computeDebugInfo(iw, op, op.info); | |
2149 | |
2150 if (op instanceof LIRXirInstruction) { | |
2151 LIRXirInstruction xir = (LIRXirInstruction) op; | |
2152 if (xir.infoAfter != null) { | |
2153 computeDebugInfo(iw, op, xir.infoAfter); | |
2154 } | |
2155 } | |
2156 } | |
2157 | |
2158 | |
2159 private void computeDebugInfo(IntervalWalker iw, LIRInstruction op, LIRDebugInfo info) { | |
2160 if (info != null) { | |
2161 if (info.debugInfo == null) { | |
2162 int frameSize = compilation.frameMap().frameSize(); | |
2163 int frameWords = frameSize / compilation.target.spillSlotSize; | |
2164 CiBitMap frameRefMap = new CiBitMap(frameWords); | |
2165 CiBitMap regRefMap = !op.hasCall ? new CiBitMap(compilation.target.arch.registerReferenceMapBitCount) : null; | |
2166 CiFrame frame = compilation.placeholderState != null ? null : computeFrame(info.state, op.id, frameRefMap); | |
2167 computeOopMap(iw, op, info, frameRefMap, regRefMap); | |
2168 info.debugInfo = new CiDebugInfo(frame, regRefMap, frameRefMap); | |
2169 } else if (C1XOptions.DetailedAsserts) { | |
2170 assert info.debugInfo.frame().equals(computeFrame(info.state, op.id, new CiBitMap(info.debugInfo.frameRefMap.size()))); | |
2171 } | |
2172 } | |
2173 } | |
2174 | |
2175 CiFrame computeFrame(FrameState state, int opId, CiBitMap frameRefMap) { | |
2176 if (C1XOptions.TraceLinearScanLevel >= 3) { | |
2177 TTY.println("creating debug information at opId %d", opId); | |
2178 } | |
2179 return computeFrameForState(opId, state, frameRefMap); | |
2180 } | |
2181 | |
2182 private void assignLocations(List<LIRInstruction> instructions, IntervalWalker iw) { | |
2183 int numInst = instructions.size(); | |
2184 boolean hasDead = false; | |
2185 | |
2186 for (int j = 0; j < numInst; j++) { | |
2187 LIRInstruction op = instructions.get(j); | |
2188 if (op == null) { // this can happen when spill-moves are removed in eliminateSpillMoves | |
2189 hasDead = true; | |
2190 continue; | |
2191 } | |
2192 | |
2193 // iterate all modes of the visitor and process all virtual operands | |
2194 for (LIRInstruction.OperandMode mode : LIRInstruction.OPERAND_MODES) { | |
2195 int n = op.operandCount(mode); | |
2196 for (int k = 0; k < n; k++) { | |
2197 CiValue operand = op.operandAt(mode, k); | |
2198 if (operand.isVariable()) { | |
2199 op.setOperandAt(mode, k, colorLirOperand((CiVariable) operand, op.id, mode)); | |
2200 } | |
2201 } | |
2202 } | |
2203 | |
2204 if (op.info != null) { | |
2205 // exception handling | |
2206 if (compilation.hasExceptionHandlers()) { | |
2207 for (ExceptionHandler handler : op.exceptionEdges()) { | |
2208 if (handler.entryCode() != null) { | |
2209 assignLocations(handler.entryCode().instructionsList(), null); | |
2210 } | |
2211 } | |
2212 } | |
2213 | |
2214 // compute reference map and debug information | |
2215 computeDebugInfo(iw, op); | |
2216 } | |
2217 | |
2218 // make sure we haven't made the op invalid. | |
2219 assert op.verify(); | |
2220 | |
2221 // remove useless moves | |
2222 if (op.code == LIROpcode.Move) { | |
2223 CiValue src = op.operand(0); | |
2224 CiValue dst = op.result(); | |
2225 if (dst == src || src.equals(dst)) { | |
2226 // TODO: what about o.f = o.f and exceptions? | |
2227 instructions.set(j, null); | |
2228 hasDead = true; | |
2229 } | |
2230 } | |
2231 } | |
2232 | |
2233 if (hasDead) { | |
2234 // iterate all instructions of the block and remove all null-values. | |
2235 int insertPoint = 0; | |
2236 for (int j = 0; j < numInst; j++) { | |
2237 LIRInstruction op = instructions.get(j); | |
2238 if (op != null) { | |
2239 if (insertPoint != j) { | |
2240 instructions.set(insertPoint, op); | |
2241 } | |
2242 insertPoint++; | |
2243 } | |
2244 } | |
2245 Util.truncate(instructions, insertPoint); | |
2246 } | |
2247 } | |
2248 | |
2249 private void assignLocations() { | |
2250 IntervalWalker iw = initComputeOopMaps(); | |
2251 for (BlockBegin block : sortedBlocks) { | |
2252 assignLocations(block.lir().instructionsList(), iw); | |
2253 } | |
2254 } | |
2255 | |
2256 public void allocate() { | |
2257 if (C1XOptions.PrintTimers) { | |
2258 C1XTimers.LIFETIME_ANALYSIS.start(); | |
2259 } | |
2260 | |
2261 numberInstructions(); | |
2262 | |
2263 printLir("Before register allocation", true); | |
2264 | |
2265 computeLocalLiveSets(); | |
2266 computeGlobalLiveSets(); | |
2267 | |
2268 buildIntervals(); | |
2269 sortIntervalsBeforeAllocation(); | |
2270 | |
2271 if (C1XOptions.PrintTimers) { | |
2272 C1XTimers.LIFETIME_ANALYSIS.stop(); | |
2273 C1XTimers.LINEAR_SCAN.start(); | |
2274 } | |
2275 | |
2276 printIntervals("Before register allocation"); | |
2277 | |
2278 allocateRegisters(); | |
2279 | |
2280 if (C1XOptions.PrintTimers) { | |
2281 C1XTimers.LINEAR_SCAN.stop(); | |
2282 C1XTimers.RESOLUTION.start(); | |
2283 } | |
2284 | |
2285 resolveDataFlow(); | |
2286 if (compilation.hasExceptionHandlers()) { | |
2287 resolveExceptionHandlers(); | |
2288 } | |
2289 | |
2290 if (C1XOptions.PrintTimers) { | |
2291 C1XTimers.RESOLUTION.stop(); | |
2292 C1XTimers.DEBUG_INFO.start(); | |
2293 } | |
2294 | |
2295 C1XMetrics.LSRASpills += (maxSpills - frameMap.initialSpillSlot()); | |
2296 | |
2297 // fill in number of spill slots into frameMap | |
2298 frameMap.finalizeFrame(maxSpills); | |
2299 | |
2300 printIntervals("After register allocation"); | |
2301 printLir("After register allocation", true); | |
2302 | |
2303 sortIntervalsAfterAllocation(); | |
2304 | |
2305 if (C1XOptions.DetailedAsserts) { | |
2306 verify(); | |
2307 } | |
2308 | |
2309 eliminateSpillMoves(); | |
2310 assignLocations(); | |
2311 | |
2312 if (C1XOptions.DetailedAsserts) { | |
2313 verifyIntervals(); | |
2314 } | |
2315 | |
2316 if (C1XOptions.PrintTimers) { | |
2317 C1XTimers.DEBUG_INFO.stop(); | |
2318 C1XTimers.CODE_CREATE.start(); | |
2319 } | |
2320 | |
2321 printLir("After register number assignment", true); | |
2322 | |
2323 EdgeMoveOptimizer.optimize(ir.linearScanOrder()); | |
2324 if (C1XOptions.OptControlFlow) { | |
2325 ControlFlowOptimizer.optimize(ir); | |
2326 } | |
2327 | |
2328 printLir("After control flow optimization", false); | |
2329 } | |
2330 | |
2331 void printIntervals(String label) { | |
2332 if (C1XOptions.TraceLinearScanLevel >= 1) { | |
2333 int i; | |
2334 TTY.println(); | |
2335 TTY.println(label); | |
2336 | |
2337 for (Interval interval : intervals) { | |
2338 if (interval != null) { | |
2339 TTY.out().println(interval.logString(this)); | |
2340 } | |
2341 } | |
2342 | |
2343 TTY.println(); | |
2344 TTY.println("--- Basic Blocks ---"); | |
2345 for (i = 0; i < blockCount(); i++) { | |
2346 BlockBegin block = blockAt(i); | |
2347 TTY.print("B%d [%d, %d, %d, %d] ", block.blockID, block.firstLirInstructionId(), block.lastLirInstructionId(), block.loopIndex(), block.loopDepth()); | |
2348 } | |
2349 TTY.println(); | |
2350 TTY.println(); | |
2351 } | |
2352 | |
2353 if (compilation.compiler.isObserved()) { | |
2354 compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, label, this, intervals, intervalsSize)); | |
2355 } | |
2356 } | |
2357 | |
2358 void printLir(String label, boolean hirValid) { | |
2359 if (C1XOptions.TraceLinearScanLevel >= 1 && !TTY.isSuppressed()) { | |
2360 TTY.println(); | |
2361 TTY.println(label); | |
2362 LIRList.printLIR(ir.linearScanOrder()); | |
2363 TTY.println(); | |
2364 } | |
2365 | |
2366 if (compilation.compiler.isObserved()) { | |
2367 compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, label, compilation.hir().startBlock, hirValid, true)); | |
2368 } | |
2369 } | |
2370 | |
2371 boolean verify() { | |
2372 // (check that all intervals have a correct register and that no registers are overwritten) | |
2373 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
2374 TTY.println(" verifying intervals *"); | |
2375 } | |
2376 verifyIntervals(); | |
2377 | |
2378 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
2379 TTY.println(" verifying that no oops are in fixed intervals *"); | |
2380 } | |
2381 //verifyNoOopsInFixedIntervals(); | |
2382 | |
2383 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
2384 TTY.println(" verifying that unpinned constants are not alive across block boundaries"); | |
2385 } | |
2386 verifyConstants(); | |
2387 | |
2388 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
2389 TTY.println(" verifying register allocation *"); | |
2390 } | |
2391 verifyRegisters(); | |
2392 | |
2393 if (C1XOptions.TraceLinearScanLevel >= 2) { | |
2394 TTY.println(" no errors found *"); | |
2395 } | |
2396 | |
2397 return true; | |
2398 } | |
2399 | |
2400 private void verifyRegisters() { | |
2401 RegisterVerifier verifier = new RegisterVerifier(this); | |
2402 verifier.verify(blockAt(0)); | |
2403 } | |
2404 | |
2405 void verifyIntervals() { | |
2406 int len = intervalsSize; | |
2407 | |
2408 for (int i = 0; i < len; i++) { | |
2409 Interval i1 = intervals[i]; | |
2410 if (i1 == null) { | |
2411 continue; | |
2412 } | |
2413 | |
2414 i1.checkSplitChildren(); | |
2415 | |
2416 if (i1.operandNumber != i) { | |
2417 TTY.println("Interval %d is on position %d in list", i1.operandNumber, i); | |
2418 TTY.println(i1.logString(this)); | |
2419 throw new CiBailout(""); | |
2420 } | |
2421 | |
2422 if (i1.operand.isVariable() && i1.kind() == CiKind.Illegal) { | |
2423 TTY.println("Interval %d has no type assigned", i1.operandNumber); | |
2424 TTY.println(i1.logString(this)); | |
2425 throw new CiBailout(""); | |
2426 } | |
2427 | |
2428 if (i1.location() == null) { | |
2429 TTY.println("Interval %d has no register assigned", i1.operandNumber); | |
2430 TTY.println(i1.logString(this)); | |
2431 throw new CiBailout(""); | |
2432 } | |
2433 | |
2434 if (!isProcessed(i1.location())) { | |
2435 TTY.println("Can not have an Interval for an ignored register " + i1.location()); | |
2436 TTY.println(i1.logString(this)); | |
2437 throw new CiBailout(""); | |
2438 } | |
2439 | |
2440 if (i1.first() == Range.EndMarker) { | |
2441 TTY.println("Interval %d has no Range", i1.operandNumber); | |
2442 TTY.println(i1.logString(this)); | |
2443 throw new CiBailout(""); | |
2444 } | |
2445 | |
2446 for (Range r = i1.first(); r != Range.EndMarker; r = r.next) { | |
2447 if (r.from >= r.to) { | |
2448 TTY.println("Interval %d has zero length range", i1.operandNumber); | |
2449 TTY.println(i1.logString(this)); | |
2450 throw new CiBailout(""); | |
2451 } | |
2452 } | |
2453 | |
2454 for (int j = i + 1; j < len; j++) { | |
2455 Interval i2 = intervals[j]; | |
2456 if (i2 == null) { | |
2457 continue; | |
2458 } | |
2459 | |
2460 // special intervals that are created in MoveResolver | |
2461 // . ignore them because the range information has no meaning there | |
2462 if (i1.from() == 1 && i1.to() == 2) { | |
2463 continue; | |
2464 } | |
2465 if (i2.from() == 1 && i2.to() == 2) { | |
2466 continue; | |
2467 } | |
2468 CiValue l1 = i1.location(); | |
2469 CiValue l2 = i2.location(); | |
2470 if (i1.intersects(i2) && (l1.equals(l2))) { | |
2471 if (C1XOptions.DetailedAsserts) { | |
2472 TTY.println("Intervals %d and %d overlap and have the same register assigned", i1.operandNumber, i2.operandNumber); | |
2473 TTY.println(i1.logString(this)); | |
2474 TTY.println(i2.logString(this)); | |
2475 } | |
2476 throw new CiBailout(""); | |
2477 } | |
2478 } | |
2479 } | |
2480 } | |
2481 | |
2482 void verifyNoOopsInFixedIntervals() { | |
2483 Interval fixedIntervals; | |
2484 Interval otherIntervals; | |
2485 fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first; | |
2486 // to ensure a walking until the last instruction id, add a dummy interval | |
2487 // with a high operation id | |
2488 otherIntervals = new Interval(CiValue.IllegalValue, -1); | |
2489 otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); | |
2490 IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals); | |
2491 | |
2492 for (int i = 0; i < blockCount(); i++) { | |
2493 BlockBegin block = blockAt(i); | |
2494 | |
2495 List<LIRInstruction> instructions = block.lir().instructionsList(); | |
2496 | |
2497 for (int j = 0; j < instructions.size(); j++) { | |
2498 LIRInstruction op = instructions.get(j); | |
2499 | |
2500 if (op.info != null) { | |
2501 iw.walkBefore(op.id); | |
2502 boolean checkLive = true; | |
2503 | |
2504 // Make sure none of the fixed registers is live across an | |
2505 // oopmap since we can't handle that correctly. | |
2506 if (checkLive) { | |
2507 for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) { | |
2508 if (interval.currentTo() > op.id + 1) { | |
2509 // This interval is live out of this op so make sure | |
2510 // that this interval represents some value that's | |
2511 // referenced by this op either as an input or output. | |
2512 boolean ok = false; | |
2513 for (LIRInstruction.OperandMode mode : LIRInstruction.OPERAND_MODES) { | |
2514 int n = op.operandCount(mode); | |
2515 for (int k = 0; k < n; k++) { | |
2516 CiValue operand = op.operandAt(mode, k); | |
2517 if (operand.isRegister()) { | |
2518 if (intervalFor(operand) == interval) { | |
2519 ok = true; | |
2520 break; | |
2521 } | |
2522 } | |
2523 } | |
2524 } | |
2525 assert ok : "fixed intervals should never be live across an oopmap point"; | |
2526 } | |
2527 } | |
2528 } | |
2529 } | |
2530 } | |
2531 } | |
2532 } | |
2533 | |
2534 void verifyConstants() { | |
2535 int numBlocks = blockCount(); | |
2536 | |
2537 for (int i = 0; i < numBlocks; i++) { | |
2538 BlockBegin block = blockAt(i); | |
2539 CiBitMap liveAtEdge = block.lirBlock.liveIn; | |
2540 | |
2541 // visit all operands where the liveAtEdge bit is set | |
2542 for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { | |
2543 if (C1XOptions.TraceLinearScanLevel >= 4) { | |
2544 TTY.println("checking interval %d of block B%d", operandNum, block.blockID); | |
2545 } | |
2546 CiValue operand = operands.operandFor(operandNum); | |
2547 assert operand.isVariable() : "value must have variable operand"; | |
2548 Value value = gen.operands.instructionForResult(((CiVariable) operand)); | |
2549 assert value != null : "all intervals live across block boundaries must have Value"; | |
2550 // TKR assert value.asConstant() == null || value.isPinned() : | |
2551 // "only pinned constants can be alive accross block boundaries"; | |
2552 } | |
2553 } | |
2554 } | |
2555 | |
2556 public int numberOfSpillSlots(CiKind kind) { | |
2557 return compilation.target.spillSlots(kind); | |
2558 } | |
2559 } |