1 /*
2 * Copyright (c) 2009, 2016, 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 org.graalvm.compiler.lir.gen;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.asConstant;
26 import static org.graalvm.compiler.lir.LIRValueUtil.asJavaConstant;
27 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
28 import static org.graalvm.compiler.lir.LIRValueUtil.isJavaConstant;
29 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
30 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
31 import static jdk.vm.ci.code.ValueUtil.asAllocatableValue;
32 import static jdk.vm.ci.code.ValueUtil.isAllocatableValue;
33 import static jdk.vm.ci.code.ValueUtil.isLegal;
34 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
35
36 import java.util.ArrayList;
37 import java.util.List;
38
39 import org.graalvm.compiler.asm.Label;
40 import org.graalvm.compiler.core.common.LIRKind;
41 import org.graalvm.compiler.core.common.calc.Condition;
42 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
43 import org.graalvm.compiler.core.common.spi.CodeGenProviders;
44 import org.graalvm.compiler.core.common.spi.ForeignCallLinkage;
45 import org.graalvm.compiler.core.common.spi.ForeignCallsProvider;
46 import org.graalvm.compiler.core.common.spi.LIRKindTool;
47 import org.graalvm.compiler.core.common.type.Stamp;
48 import org.graalvm.compiler.debug.GraalError;
49 import org.graalvm.compiler.debug.TTY;
50 import org.graalvm.compiler.graph.NodeSourcePosition;
51 import org.graalvm.compiler.lir.ConstantValue;
52 import org.graalvm.compiler.lir.LIRFrameState;
53 import org.graalvm.compiler.lir.LIRInstruction;
54 import org.graalvm.compiler.lir.LIRVerifier;
55 import org.graalvm.compiler.lir.LabelRef;
56 import org.graalvm.compiler.lir.StandardOp;
57 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
58 import org.graalvm.compiler.lir.StandardOp.LabelOp;
59 import org.graalvm.compiler.lir.StandardOp.SaveRegistersOp;
60 import org.graalvm.compiler.lir.SwitchStrategy;
61 import org.graalvm.compiler.lir.Variable;
62 import org.graalvm.compiler.options.Option;
63 import org.graalvm.compiler.options.OptionType;
64 import org.graalvm.compiler.options.OptionValue;
65
66 import jdk.vm.ci.code.CallingConvention;
67 import jdk.vm.ci.code.CodeCacheProvider;
68 import jdk.vm.ci.code.Register;
69 import jdk.vm.ci.code.RegisterAttributes;
70 import jdk.vm.ci.code.StackSlot;
71 import jdk.vm.ci.code.TargetDescription;
72 import jdk.vm.ci.meta.AllocatableValue;
73 import jdk.vm.ci.meta.Constant;
74 import jdk.vm.ci.meta.JavaConstant;
75 import jdk.vm.ci.meta.JavaKind;
76 import jdk.vm.ci.meta.MetaAccessProvider;
77 import jdk.vm.ci.meta.PlatformKind;
78 import jdk.vm.ci.meta.Value;
79 import jdk.vm.ci.meta.ValueKind;
80
81 /**
82 * This class traverses the HIR instructions and generates LIR instructions from them.
83 */
84 public abstract class LIRGenerator implements LIRGeneratorTool {
85
86 public static class Options {
87 // @formatter:off
88 @Option(help = "Print HIR along side LIR as the latter is generated", type = OptionType.Debug)
89 public static final OptionValue<Boolean> PrintIRWithLIR = new OptionValue<>(false);
90 @Option(help = "The trace level for the LIR generator", type = OptionType.Debug)
91 public static final OptionValue<Integer> TraceLIRGeneratorLevel = new OptionValue<>(0);
92 // @formatter:on
93 }
94
95 private final LIRKindTool lirKindTool;
96
97 private final CodeGenProviders providers;
98
99 private AbstractBlockBase<?> currentBlock;
100
101 private LIRGenerationResult res;
102
103 protected final ArithmeticLIRGenerator arithmeticLIRGen;
104 private final MoveFactory moveFactory;
105
106 public LIRGenerator(LIRKindTool lirKindTool, ArithmeticLIRGenerator arithmeticLIRGen, MoveFactory moveFactory, CodeGenProviders providers, LIRGenerationResult res) {
107 this.lirKindTool = lirKindTool;
108 this.arithmeticLIRGen = arithmeticLIRGen;
109 this.res = res;
110 this.providers = providers;
111
112 assert arithmeticLIRGen.lirGen == null;
113 arithmeticLIRGen.lirGen = this;
114 this.moveFactory = moveFactory;
115 }
116
117 @Override
118 public ArithmeticLIRGeneratorTool getArithmetic() {
119 return arithmeticLIRGen;
120 }
121
122 @Override
123 public MoveFactory getMoveFactory() {
124 return moveFactory;
125 }
126
127 private MoveFactory spillMoveFactory;
128
129 @Override
130 public MoveFactory getSpillMoveFactory() {
131 if (spillMoveFactory == null) {
132 boolean verify = false;
133 assert (verify = true) == true;
134 if (verify) {
135 spillMoveFactory = new VerifyingMoveFactory(moveFactory);
136 } else {
137 spillMoveFactory = moveFactory;
138 }
139 }
140 return spillMoveFactory;
141 }
142
143 @Override
144 public LIRKind getValueKind(JavaKind javaKind) {
145 return LIRKind.fromJavaKind(target().arch, javaKind);
146 }
147
148 @Override
149 public TargetDescription target() {
150 return getCodeCache().getTarget();
151 }
152
153 @Override
154 public CodeGenProviders getProviders() {
155 return providers;
156 }
157
158 @Override
159 public MetaAccessProvider getMetaAccess() {
160 return providers.getMetaAccess();
161 }
162
163 @Override
164 public CodeCacheProvider getCodeCache() {
165 return providers.getCodeCache();
166 }
167
168 @Override
169 public ForeignCallsProvider getForeignCalls() {
170 return providers.getForeignCalls();
171 }
172
173 public LIRKindTool getLIRKindTool() {
174 return lirKindTool;
175 }
176
177 /**
178 * Hide {@link #nextVariable()} from other users.
179 */
180 public abstract static class VariableProvider {
181 private int numVariables;
182
183 public int numVariables() {
184 return numVariables;
185 }
186
187 private int nextVariable() {
188 return numVariables++;
189 }
190 }
191
192 @Override
193 public Variable newVariable(ValueKind<?> valueKind) {
194 return new Variable(valueKind, ((VariableProvider) res.getLIR()).nextVariable());
195 }
196
197 @Override
198 public RegisterAttributes attributes(Register register) {
199 return res.getFrameMapBuilder().getRegisterConfig().getAttributesMap()[register.number];
200 }
201
202 @Override
203 public Variable emitMove(Value input) {
204 assert !(input instanceof Variable) : "Creating a copy of a variable via this method is not supported (and potentially a bug): " + input;
205 Variable result = newVariable(input.getValueKind());
206 emitMove(result, input);
207 return result;
208 }
209
210 @Override
211 public void emitMove(AllocatableValue dst, Value src) {
212 append(moveFactory.createMove(dst, src));
213 }
214
215 @Override
216 public void emitMoveConstant(AllocatableValue dst, Constant src) {
217 append(moveFactory.createLoad(dst, src));
218 }
219
220 @Override
221 public Value emitConstant(LIRKind kind, Constant constant) {
222 if (constant instanceof JavaConstant && moveFactory.canInlineConstant((JavaConstant) constant)) {
223 return new ConstantValue(toRegisterKind(kind), constant);
224 } else {
225 return emitLoadConstant(kind, constant);
226 }
227 }
228
229 @Override
230 public Value emitJavaConstant(JavaConstant constant) {
231 return emitConstant(getValueKind(constant.getJavaKind()), constant);
232 }
233
234 @Override
235 public AllocatableValue emitLoadConstant(ValueKind<?> kind, Constant constant) {
236 Variable result = newVariable(kind);
237 emitMoveConstant(result, constant);
238 return result;
239 }
240
241 @Override
242 public AllocatableValue asAllocatable(Value value) {
243 if (isAllocatableValue(value)) {
244 return asAllocatableValue(value);
245 } else if (isConstantValue(value)) {
246 return emitLoadConstant(value.getValueKind(), asConstant(value));
247 } else {
248 return emitMove(value);
249 }
250 }
251
252 @Override
253 public Variable load(Value value) {
254 if (!isVariable(value)) {
255 return emitMove(value);
256 }
257 return (Variable) value;
258 }
259
260 @Override
261 public Value loadNonConst(Value value) {
262 if (isJavaConstant(value) && !moveFactory.canInlineConstant(asJavaConstant(value))) {
263 return emitMove(value);
264 }
265 return value;
266 }
267
268 /**
269 * Determines if only oop maps are required for the code generated from the LIR.
270 */
271 @Override
272 public boolean needOnlyOopMaps() {
273 return false;
274 }
275
276 /**
277 * Gets the ABI specific operand used to return a value of a given kind from a method.
278 *
279 * @param javaKind the kind of value being returned
280 * @param valueKind the backend type of the value being returned
281 * @return the operand representing the ABI defined location used return a value of kind
282 * {@code kind}
283 */
284 @Override
285 public AllocatableValue resultOperandFor(JavaKind javaKind, ValueKind<?> valueKind) {
286 Register reg = res.getFrameMapBuilder().getRegisterConfig().getReturnRegister(javaKind);
287 assert target().arch.canStoreValue(reg.getRegisterCategory(), valueKind.getPlatformKind()) : reg.getRegisterCategory() + " " + valueKind.getPlatformKind();
288 return reg.asValue(valueKind);
289 }
290
291 NodeSourcePosition currentPosition;
292
293 @Override
294 public void setSourcePosition(NodeSourcePosition position) {
295 currentPosition = position;
296 }
297
298 @Override
299 public <I extends LIRInstruction> I append(I op) {
300 if (Options.PrintIRWithLIR.getValue() && !TTY.isSuppressed()) {
301 TTY.println(op.toStringWithIdPrefix());
302 TTY.println();
303 }
304 assert LIRVerifier.verify(op);
305 List<LIRInstruction> lirForBlock = res.getLIR().getLIRforBlock(getCurrentBlock());
306 op.setPosition(currentPosition);
307 lirForBlock.add(op);
308 return op;
309 }
310
311 @Override
312 public boolean hasBlockEnd(AbstractBlockBase<?> block) {
313 List<LIRInstruction> ops = getResult().getLIR().getLIRforBlock(block);
314 if (ops.size() == 0) {
315 return false;
316 }
317 return ops.get(ops.size() - 1) instanceof BlockEndOp;
318 }
319
320 private final class BlockScopeImpl extends BlockScope {
321
322 private BlockScopeImpl(AbstractBlockBase<?> block) {
323 currentBlock = block;
324 }
325
326 private void doBlockStart() {
327 if (Options.PrintIRWithLIR.getValue()) {
328 TTY.print(currentBlock.toString());
329 }
330
331 // set up the list of LIR instructions
332 assert res.getLIR().getLIRforBlock(currentBlock) == null : "LIR list already computed for this block";
333 res.getLIR().setLIRforBlock(currentBlock, new ArrayList<LIRInstruction>());
334
335 append(new LabelOp(new Label(currentBlock.getId()), currentBlock.isAligned()));
336
337 if (Options.TraceLIRGeneratorLevel.getValue() >= 1) {
338 TTY.println("BEGIN Generating LIR for block B" + currentBlock.getId());
339 }
340 }
341
342 private void doBlockEnd() {
343 if (Options.TraceLIRGeneratorLevel.getValue() >= 1) {
344 TTY.println("END Generating LIR for block B" + currentBlock.getId());
345 }
346
347 if (Options.PrintIRWithLIR.getValue()) {
348 TTY.println();
349 }
350 currentBlock = null;
351 }
352
353 @Override
354 public AbstractBlockBase<?> getCurrentBlock() {
355 return currentBlock;
356 }
357
358 @Override
359 public void close() {
360 doBlockEnd();
361 }
362
363 }
364
365 @Override
366 public final BlockScope getBlockScope(AbstractBlockBase<?> block) {
367 BlockScopeImpl blockScope = new BlockScopeImpl(block);
368 blockScope.doBlockStart();
369 return blockScope;
370 }
371
372 @Override
373 public void emitIncomingValues(Value[] params) {
374 ((LabelOp) res.getLIR().getLIRforBlock(getCurrentBlock()).get(0)).setIncomingValues(params);
375 }
376
377 @Override
378 public abstract void emitJump(LabelRef label);
379
380 @Override
381 public abstract void emitCompareBranch(PlatformKind cmpKind, Value left, Value right, Condition cond, boolean unorderedIsTrue, LabelRef trueDestination, LabelRef falseDestination,
382 double trueDestinationProbability);
383
384 @Override
385 public abstract void emitOverflowCheckBranch(LabelRef overflow, LabelRef noOverflow, LIRKind cmpKind, double overflowProbability);
386
387 @Override
388 public abstract void emitIntegerTestBranch(Value left, Value right, LabelRef trueDestination, LabelRef falseDestination, double trueSuccessorProbability);
389
390 @Override
391 public abstract Variable emitConditionalMove(PlatformKind cmpKind, Value leftVal, Value right, Condition cond, boolean unorderedIsTrue, Value trueValue, Value falseValue);
392
393 @Override
394 public abstract Variable emitIntegerTestMove(Value leftVal, Value right, Value trueValue, Value falseValue);
395
396 /**
397 * Emits the single call operation at the heart of generating LIR for a
398 * {@linkplain #emitForeignCall(ForeignCallLinkage, LIRFrameState, Value...) foreign call}.
399 */
400 protected abstract void emitForeignCallOp(ForeignCallLinkage linkage, Value result, Value[] arguments, Value[] temps, LIRFrameState info);
401
402 @Override
403 public Variable emitForeignCall(ForeignCallLinkage linkage, LIRFrameState frameState, Value... args) {
404 LIRFrameState state = null;
405 if (linkage.needsDebugInfo()) {
406 if (frameState != null) {
407 state = frameState;
408 } else {
409 assert needOnlyOopMaps();
410 state = new LIRFrameState(null, null, null);
411 }
412 }
413
414 // move the arguments into the correct location
415 CallingConvention linkageCc = linkage.getOutgoingCallingConvention();
416 res.getFrameMapBuilder().callsMethod(linkageCc);
417 assert linkageCc.getArgumentCount() == args.length : "argument count mismatch";
418 Value[] argLocations = new Value[args.length];
419 for (int i = 0; i < args.length; i++) {
420 Value arg = args[i];
421 AllocatableValue loc = linkageCc.getArgument(i);
422 emitMove(loc, arg);
423 argLocations[i] = loc;
424 }
425 res.setForeignCall(true);
426 emitForeignCallOp(linkage, linkageCc.getReturn(), argLocations, linkage.getTemporaries(), state);
427
428 if (isLegal(linkageCc.getReturn())) {
429 return emitMove(linkageCc.getReturn());
430 } else {
431 return null;
432 }
433 }
434
435 @Override
436 public void emitStrategySwitch(JavaConstant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) {
437 int keyCount = keyConstants.length;
438 SwitchStrategy strategy = SwitchStrategy.getBestStrategy(keyProbabilities, keyConstants, keyTargets);
439 long valueRange = keyConstants[keyCount - 1].asLong() - keyConstants[0].asLong() + 1;
440 double tableSwitchDensity = keyCount / (double) valueRange;
441 /*
442 * This heuristic tries to find a compromise between the effort for the best switch strategy
443 * and the density of a tableswitch. If the effort for the strategy is at least 4, then a
444 * tableswitch is preferred if better than a certain value that starts at 0.5 and lowers
445 * gradually with additional effort.
446 */
447 if (strategy.getAverageEffort() < 4 || tableSwitchDensity < (1 / Math.sqrt(strategy.getAverageEffort()))) {
448 emitStrategySwitch(strategy, value, keyTargets, defaultTarget);
449 } else {
450 int minValue = keyConstants[0].asInt();
451 assert valueRange < Integer.MAX_VALUE;
452 LabelRef[] targets = new LabelRef[(int) valueRange];
453 for (int i = 0; i < valueRange; i++) {
454 targets[i] = defaultTarget;
455 }
456 for (int i = 0; i < keyCount; i++) {
457 targets[keyConstants[i].asInt() - minValue] = keyTargets[i];
458 }
459 emitTableSwitch(minValue, defaultTarget, targets, value);
460 }
461 }
462
463 @Override
464 public abstract void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget);
465
466 protected abstract void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key);
467
468 @Override
469 public void beforeRegisterAllocation() {
470 }
471
472 /**
473 * Gets a garbage value for a given kind.
474 */
475 protected abstract JavaConstant zapValueForKind(PlatformKind kind);
476
477 @Override
478 public LIRKind getLIRKind(Stamp stamp) {
479 return stamp.getLIRKind(lirKindTool);
480 }
481
482 protected LIRKind getAddressKind(Value base, long displacement, Value index) {
483 if (LIRKind.isValue(base) && (index.equals(Value.ILLEGAL) || LIRKind.isValue(index))) {
484 return LIRKind.value(target().arch.getWordKind());
485 } else if (base.getValueKind() instanceof LIRKind && base.getValueKind(LIRKind.class).isReference(0) && displacement == 0L && index.equals(Value.ILLEGAL)) {
486 return LIRKind.reference(target().arch.getWordKind());
487 } else {
488 return LIRKind.unknownReference(target().arch.getWordKind());
489 }
490 }
491
492 @Override
493 public AbstractBlockBase<?> getCurrentBlock() {
494 return currentBlock;
495 }
496
497 @Override
498 public LIRGenerationResult getResult() {
499 return res;
500 }
501
502 @Override
503 public void emitBlackhole(Value operand) {
504 append(new StandardOp.BlackholeOp(operand));
505 }
506
507 @Override
508 public LIRInstruction createBenchmarkCounter(String name, String group, Value increment) {
509 throw GraalError.unimplemented();
510 }
511
512 @Override
513 public LIRInstruction createMultiBenchmarkCounter(String[] names, String[] groups, Value[] increments) {
514 throw GraalError.unimplemented();
515 }
516
517 @Override
518 public abstract SaveRegistersOp createZapRegisters(Register[] zappedRegisters, JavaConstant[] zapValues);
519
520 @Override
521 public SaveRegistersOp createZapRegisters() {
522 Register[] zappedRegisters = getResult().getFrameMap().getRegisterConfig().getAllocatableRegisters().toArray();
523 JavaConstant[] zapValues = new JavaConstant[zappedRegisters.length];
524 for (int i = 0; i < zappedRegisters.length; i++) {
525 PlatformKind kind = target().arch.getLargestStorableKind(zappedRegisters[i].getRegisterCategory());
526 zapValues[i] = zapValueForKind(kind);
527 }
528 return createZapRegisters(zappedRegisters, zapValues);
529 }
530
531 @Override
532 public abstract LIRInstruction createZapArgumentSpace(StackSlot[] zappedStack, JavaConstant[] zapValues);
533
534 @Override
535 public LIRInstruction zapArgumentSpace() {
536 List<StackSlot> slots = null;
537 for (AllocatableValue arg : res.getCallingConvention().getArguments()) {
538 if (isStackSlot(arg)) {
539 if (slots == null) {
540 slots = new ArrayList<>();
541 }
542 slots.add((StackSlot) arg);
543 } else {
544 assert !isVirtualStackSlot(arg);
545 }
546 }
547 if (slots == null) {
548 return null;
549 }
550 StackSlot[] zappedStack = slots.toArray(new StackSlot[slots.size()]);
551 JavaConstant[] zapValues = new JavaConstant[zappedStack.length];
552 for (int i = 0; i < zappedStack.length; i++) {
553 PlatformKind kind = zappedStack[i].getPlatformKind();
554 zapValues[i] = zapValueForKind(kind);
555 }
556 return createZapArgumentSpace(zappedStack, zapValues);
557 }
558 }