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