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