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 }