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