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.core.gen;
  26 
  27 import static jdk.vm.ci.code.ValueUtil.asRegister;
  28 import static jdk.vm.ci.code.ValueUtil.isLegal;
  29 import static jdk.vm.ci.code.ValueUtil.isRegister;
  30 import static org.graalvm.compiler.core.common.SpeculativeExecutionAttacksMitigations.AllTargets;
  31 import static org.graalvm.compiler.core.common.SpeculativeExecutionAttacksMitigations.Options.MitigateSpeculativeExecutionAttacks;
  32 import static org.graalvm.compiler.core.common.GraalOptions.MatchExpressions;
  33 import static org.graalvm.compiler.debug.DebugOptions.LogVerbose;
  34 import static org.graalvm.compiler.lir.LIR.verifyBlock;
  35 
  36 import java.util.ArrayList;
  37 import java.util.Collection;
  38 import java.util.List;
  39 
  40 import jdk.internal.vm.compiler.collections.EconomicMap;
  41 import jdk.internal.vm.compiler.collections.UnmodifiableMapCursor;
  42 import org.graalvm.compiler.core.common.LIRKind;
  43 import org.graalvm.compiler.core.common.calc.Condition;
  44 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  45 import org.graalvm.compiler.core.common.cfg.BlockMap;
  46 import org.graalvm.compiler.core.common.type.Stamp;
  47 import org.graalvm.compiler.core.match.ComplexMatchValue;
  48 import org.graalvm.compiler.core.match.MatchPattern;
  49 import org.graalvm.compiler.core.match.MatchRuleRegistry;
  50 import org.graalvm.compiler.core.match.MatchStatement;
  51 import org.graalvm.compiler.debug.DebugContext;
  52 import org.graalvm.compiler.debug.GraalError;
  53 import org.graalvm.compiler.debug.TTY;
  54 import org.graalvm.compiler.graph.GraalGraphError;
  55 import org.graalvm.compiler.graph.Node;
  56 import org.graalvm.compiler.graph.NodeMap;
  57 import org.graalvm.compiler.graph.NodeSourcePosition;
  58 import org.graalvm.compiler.graph.iterators.NodeIterable;
  59 import org.graalvm.compiler.lir.FullInfopointOp;
  60 import org.graalvm.compiler.lir.LIRFrameState;
  61 import org.graalvm.compiler.lir.LIRInstruction;
  62 import org.graalvm.compiler.lir.LabelRef;
  63 import org.graalvm.compiler.lir.StandardOp.JumpOp;
  64 import org.graalvm.compiler.lir.StandardOp.LabelOp;
  65 import org.graalvm.compiler.lir.SwitchStrategy;
  66 import org.graalvm.compiler.lir.Variable;
  67 import org.graalvm.compiler.lir.debug.LIRGenerationDebugContext;
  68 import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
  69 import org.graalvm.compiler.lir.gen.LIRGenerator;
  70 import org.graalvm.compiler.lir.gen.LIRGenerator.Options;
  71 import org.graalvm.compiler.lir.gen.LIRGeneratorTool;
  72 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.BlockScope;
  73 import org.graalvm.compiler.nodes.AbstractBeginNode;
  74 import org.graalvm.compiler.nodes.AbstractEndNode;
  75 import org.graalvm.compiler.nodes.AbstractMergeNode;
  76 import org.graalvm.compiler.nodes.DeoptimizingNode;
  77 import org.graalvm.compiler.nodes.DirectCallTargetNode;
  78 import org.graalvm.compiler.nodes.FixedNode;
  79 import org.graalvm.compiler.nodes.FrameState;
  80 import org.graalvm.compiler.nodes.FullInfopointNode;
  81 import org.graalvm.compiler.nodes.IfNode;
  82 import org.graalvm.compiler.nodes.IndirectCallTargetNode;
  83 import org.graalvm.compiler.nodes.Invoke;
  84 import org.graalvm.compiler.nodes.InvokeWithExceptionNode;
  85 import org.graalvm.compiler.nodes.LogicConstantNode;
  86 import org.graalvm.compiler.nodes.LogicNode;
  87 import org.graalvm.compiler.nodes.LoopEndNode;
  88 import org.graalvm.compiler.nodes.LoweredCallTargetNode;
  89 import org.graalvm.compiler.nodes.NodeView;
  90 import org.graalvm.compiler.nodes.ParameterNode;
  91 import org.graalvm.compiler.nodes.PhiNode;
  92 import org.graalvm.compiler.nodes.StructuredGraph;
  93 import org.graalvm.compiler.nodes.ValueNode;
  94 import org.graalvm.compiler.nodes.ValuePhiNode;
  95 import org.graalvm.compiler.nodes.calc.CompareNode;
  96 import org.graalvm.compiler.nodes.calc.ConditionalNode;
  97 import org.graalvm.compiler.nodes.calc.IntegerTestNode;
  98 import org.graalvm.compiler.nodes.calc.IsNullNode;
  99 import org.graalvm.compiler.nodes.cfg.Block;
 100 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
 101 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
 102 import org.graalvm.compiler.nodes.extended.SwitchNode;
 103 import org.graalvm.compiler.nodes.spi.LIRLowerable;
 104 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
 105 import org.graalvm.compiler.nodes.spi.NodeValueMap;
 106 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
 107 import org.graalvm.compiler.options.OptionValues;
 108 
 109 import jdk.vm.ci.code.CallingConvention;
 110 import jdk.vm.ci.code.StackSlot;
 111 import jdk.vm.ci.code.ValueUtil;
 112 import jdk.vm.ci.meta.AllocatableValue;
 113 import jdk.vm.ci.meta.Constant;
 114 import jdk.vm.ci.meta.JavaConstant;
 115 import jdk.vm.ci.meta.JavaKind;
 116 import jdk.vm.ci.meta.PlatformKind;
 117 import jdk.vm.ci.meta.Value;
 118 
 119 /**
 120  * This class traverses the HIR instructions and generates LIR instructions from them.
 121  */
 122 public abstract class NodeLIRBuilder implements NodeLIRBuilderTool, LIRGenerationDebugContext {
 123 
 124     private final NodeMap<Value> nodeOperands;
 125     private final DebugInfoBuilder debugInfoBuilder;
 126     private final int traceLIRGeneratorLevel;
 127 
 128     protected final LIRGenerator gen;
 129 
 130     private ValueNode currentInstruction;
 131     private ValueNode lastInstructionPrinted; // Debugging only
 132 
 133     private final NodeMatchRules nodeMatchRules;
 134     private EconomicMap<Class<? extends Node>, List<MatchStatement>> matchRules;
 135 
 136     public NodeLIRBuilder(StructuredGraph graph, LIRGeneratorTool gen, NodeMatchRules nodeMatchRules) {
 137         this.gen = (LIRGenerator) gen;
 138         this.nodeMatchRules = nodeMatchRules;
 139         this.nodeOperands = graph.createNodeMap();
 140         this.debugInfoBuilder = createDebugInfoBuilder(graph, this);
 141         OptionValues options = graph.getOptions();
 142         if (MatchExpressions.getValue(options)) {
 143             matchRules = MatchRuleRegistry.lookup(nodeMatchRules.getClass(), options, graph.getDebug());
 144         }
 145         traceLIRGeneratorLevel = TTY.isSuppressed() ? 0 : Options.TraceLIRGeneratorLevel.getValue(options);
 146 
 147         assert nodeMatchRules.lirBuilder == null;
 148         nodeMatchRules.lirBuilder = this;
 149     }
 150 
 151     public NodeMatchRules getNodeMatchRules() {
 152         return nodeMatchRules;
 153     }
 154 
 155     protected DebugInfoBuilder createDebugInfoBuilder(StructuredGraph graph, NodeValueMap nodeValueMap) {
 156         return new DebugInfoBuilder(nodeValueMap, graph.getDebug());
 157     }
 158 
 159     /**
 160      * Returns the operand that has been previously initialized by
 161      * {@link #setResult(ValueNode, Value)} with the result of an instruction. It's a code
 162      * generation error to ask for the operand of ValueNode that doesn't have one yet.
 163      *
 164      * @param node A node that produces a result value.
 165      */
 166     @Override
 167     public Value operand(Node node) {
 168         Value operand = getOperand(node);
 169         assert operand != null : String.format("missing operand for %1s", node);
 170         return operand;
 171     }
 172 
 173     @Override
 174     public boolean hasOperand(Node node) {
 175         return getOperand(node) != null;
 176     }
 177 
 178     private Value getOperand(Node node) {
 179         if (nodeOperands == null) {
 180             return null;
 181         }
 182         return nodeOperands.get(node);
 183     }
 184 
 185     @Override
 186     public ValueNode valueForOperand(Value value) {
 187         assert nodeOperands != null;
 188         UnmodifiableMapCursor<Node, Value> cursor = nodeOperands.getEntries();
 189         while (cursor.advance()) {
 190             if (cursor.getValue().equals(value)) {
 191                 return (ValueNode) cursor.getKey();
 192             }
 193         }
 194         return null;
 195     }
 196 
 197     @Override
 198     public Object getSourceForOperand(Value value) {
 199         return valueForOperand(value);
 200     }
 201 
 202     @Override
 203     public Value setResult(ValueNode x, Value operand) {
 204         assert (!isRegister(operand) || !gen.attributes(asRegister(operand)).isAllocatable());
 205         assert nodeOperands != null && (nodeOperands.get(x) == null || nodeOperands.get(x) instanceof ComplexMatchValue) : "operand cannot be set twice";
 206         assert operand != null && isLegal(operand) : "operand must be legal";
 207         assert !(x instanceof VirtualObjectNode);
 208         nodeOperands.set(x, operand);
 209         return operand;
 210     }
 211 
 212     /**
 213      * Used by the {@link MatchStatement} machinery to override the generation LIR for some
 214      * ValueNodes.
 215      */
 216     public void setMatchResult(Node x, Value operand) {
 217         assert operand.equals(ComplexMatchValue.INTERIOR_MATCH) || operand instanceof ComplexMatchValue;
 218         assert operand instanceof ComplexMatchValue || MatchPattern.isSingleValueUser(x) : "interior matches must be single user";
 219         assert nodeOperands != null && nodeOperands.get(x) == null : "operand cannot be set twice";
 220         assert !(x instanceof VirtualObjectNode);
 221         nodeOperands.set(x, operand);
 222     }
 223 
 224     public LabelRef getLIRBlock(FixedNode b) {
 225         assert gen.getResult().getLIR().getControlFlowGraph() instanceof ControlFlowGraph;
 226         Block result = ((ControlFlowGraph) gen.getResult().getLIR().getControlFlowGraph()).blockFor(b);
 227         int suxIndex = 0;
 228         for (AbstractBlockBase<?> succ : gen.getCurrentBlock().getSuccessors()) {
 229             if (succ == result) {
 230                 assert gen.getCurrentBlock() instanceof Block;
 231                 return LabelRef.forSuccessor(gen.getResult().getLIR(), gen.getCurrentBlock(), suxIndex);
 232             }
 233             suxIndex++;
 234         }
 235         throw GraalError.shouldNotReachHere("Block not in successor list of current block");
 236     }
 237 
 238     public final void append(LIRInstruction op) {
 239         if (Options.PrintIRWithLIR.getValue(nodeOperands.graph().getOptions()) && !TTY.isSuppressed()) {
 240             if (currentInstruction != null && lastInstructionPrinted != currentInstruction) {
 241                 lastInstructionPrinted = currentInstruction;
 242                 InstructionPrinter ip = new InstructionPrinter(TTY.out());
 243                 ip.printInstructionListing(currentInstruction);
 244             }
 245         }
 246         gen.append(op);
 247     }
 248 
 249     protected LIRKind getExactPhiKind(PhiNode phi) {
 250         LIRKind derivedKind = gen.toRegisterKind(gen.getLIRKind(phi.stamp(NodeView.DEFAULT)));
 251         /* Collect reference information. */
 252         for (int i = 0; i < phi.valueCount() && !derivedKind.isUnknownReference(); i++) {
 253             ValueNode node = phi.valueAt(i);
 254             Value value = getOperand(node);
 255 
 256             // get ValueKind for input
 257             final LIRKind valueKind;
 258             if (value != null) {
 259                 valueKind = value.getValueKind(LIRKind.class);
 260             } else {
 261                 assert isPhiInputFromBackedge(phi, i) : String.format("Input %s to phi node %s is not yet available although it is not coming from a loop back edge", node, phi);
 262                 LIRKind kind = gen.getLIRKind(node.stamp(NodeView.DEFAULT));
 263                 valueKind = gen.toRegisterKind(kind);
 264             }
 265             /* Merge the reference information of the derived kind and the input. */
 266             derivedKind = LIRKind.mergeReferenceInformation(derivedKind, valueKind);
 267         }
 268         return derivedKind;
 269     }
 270 
 271     private static boolean isPhiInputFromBackedge(PhiNode phi, int index) {
 272         AbstractMergeNode merge = phi.merge();
 273         AbstractEndNode end = merge.phiPredecessorAt(index);
 274         return end instanceof LoopEndNode && ((LoopEndNode) end).loopBegin().equals(merge);
 275     }
 276 
 277     private Value[] createPhiIn(AbstractMergeNode merge) {
 278         List<Value> values = new ArrayList<>();
 279         for (ValuePhiNode phi : merge.valuePhis()) {
 280             assert getOperand(phi) == null;
 281             Variable value = gen.newVariable(getExactPhiKind(phi));
 282             values.add(value);
 283             setResult(phi, value);
 284         }
 285         return values.toArray(new Value[values.size()]);
 286     }
 287 
 288     private Value[] createPhiOut(AbstractMergeNode merge, AbstractEndNode pred) {
 289         List<Value> values = new ArrayList<>();
 290         for (PhiNode phi : merge.valuePhis()) {
 291             ValueNode node = phi.valueAt(pred);
 292             Value value = operand(node);
 293             assert value != null;
 294             if (isRegister(value)) {
 295                 /*
 296                  * Fixed register intervals are not allowed at block boundaries so we introduce a
 297                  * new Variable.
 298                  */
 299                 value = gen.emitMove(value);
 300             } else if (node.isConstant() && !gen.getSpillMoveFactory().allowConstantToStackMove(node.asConstant()) && !LIRKind.isValue(value)) {
 301                 /*
 302                  * Some constants are not allowed as inputs for PHIs in certain backends. Explicitly
 303                  * create a copy of this value to force it into a register. The new variable is only
 304                  * used in the PHI.
 305                  */
 306                 Variable result = gen.newVariable(value.getValueKind());
 307                 gen.emitMove(result, value);
 308                 value = result;
 309             }
 310             values.add(value);
 311         }
 312         return values.toArray(new Value[values.size()]);
 313     }
 314 
 315     public void doBlockPrologue(@SuppressWarnings("unused") Block block, @SuppressWarnings("unused") OptionValues options) {
 316 
 317         if (MitigateSpeculativeExecutionAttacks.getValue(options) == AllTargets) {
 318             boolean hasControlSplitPredecessor = false;
 319             for (Block b : block.getPredecessors()) {
 320                 if (b.getSuccessorCount() > 1) {
 321                     hasControlSplitPredecessor = true;
 322                     break;
 323                 }
 324             }
 325             boolean isStartBlock = block.getPredecessorCount() == 0;
 326             if (hasControlSplitPredecessor || isStartBlock) {
 327                 getLIRGeneratorTool().emitSpeculationFence();
 328             }
 329         }
 330     }
 331 
 332     @Override
 333     @SuppressWarnings("try")
 334     public void doBlock(Block block, StructuredGraph graph, BlockMap<List<Node>> blockMap) {
 335 
 336         OptionValues options = graph.getOptions();
 337         try (BlockScope blockScope = gen.getBlockScope(block)) {
 338             setSourcePosition(null);
 339 
 340             if (block == gen.getResult().getLIR().getControlFlowGraph().getStartBlock()) {
 341                 assert block.getPredecessorCount() == 0;
 342                 emitPrologue(graph);
 343             } else {
 344                 assert block.getPredecessorCount() > 0;
 345                 // create phi-in value array
 346                 AbstractBeginNode begin = block.getBeginNode();
 347                 if (begin instanceof AbstractMergeNode) {
 348                     AbstractMergeNode merge = (AbstractMergeNode) begin;
 349                     LabelOp label = (LabelOp) gen.getResult().getLIR().getLIRforBlock(block).get(0);
 350                     label.setPhiValues(createPhiIn(merge));
 351                     if (Options.PrintIRWithLIR.getValue(options) && !TTY.isSuppressed()) {
 352                         TTY.println("Created PhiIn: " + label);
 353 
 354                     }
 355                 }
 356             }
 357             doBlockPrologue(block, options);
 358 
 359             List<Node> nodes = blockMap.get(block);
 360 
 361             // Allow NodeLIRBuilder subclass to specialize code generation of any interesting groups
 362             // of instructions
 363             matchComplexExpressions(nodes);
 364 
 365             boolean trace = traceLIRGeneratorLevel >= 3;
 366             for (int i = 0; i < nodes.size(); i++) {
 367                 Node node = nodes.get(i);
 368                 if (node instanceof ValueNode) {
 369                     setSourcePosition(node.getNodeSourcePosition());
 370                     DebugContext debug = node.getDebug();
 371                     ValueNode valueNode = (ValueNode) node;
 372                     if (trace) {
 373                         TTY.println("LIRGen for " + valueNode);
 374                     }
 375                     Value operand = getOperand(valueNode);
 376                     if (operand == null) {
 377                         if (!peephole(valueNode)) {
 378                             try {
 379                                 doRoot(valueNode);
 380                             } catch (GraalError e) {
 381                                 throw GraalGraphError.transformAndAddContext(e, valueNode);
 382                             } catch (Throwable e) {
 383                                 throw new GraalGraphError(e).addContext(valueNode);
 384                             }
 385                         }
 386                     } else if (ComplexMatchValue.INTERIOR_MATCH.equals(operand)) {
 387                         // Doesn't need to be evaluated
 388                         debug.log("interior match for %s", valueNode);
 389                     } else if (operand instanceof ComplexMatchValue) {
 390                         debug.log("complex match for %s", valueNode);
 391                         // Set current position to the position of the root matched node.
 392                         setSourcePosition(node.getNodeSourcePosition());
 393                         ComplexMatchValue match = (ComplexMatchValue) operand;
 394                         operand = match.evaluate(this);
 395                         if (operand != null) {
 396                             setResult(valueNode, operand);
 397                         }
 398                     } else {
 399                         // There can be cases in which the result of an instruction is already set
 400                         // before by other instructions.
 401                     }
 402                 }
 403             }
 404 
 405             if (!gen.hasBlockEnd(block)) {
 406                 NodeIterable<Node> successors = block.getEndNode().successors();
 407                 assert successors.count() == block.getSuccessorCount();
 408                 if (block.getSuccessorCount() != 1) {
 409                     /*
 410                      * If we have more than one successor, we cannot just use the first one. Since
 411                      * successors are unordered, this would be a random choice.
 412                      */
 413                     throw new GraalError("Block without BlockEndOp: " + block.getEndNode());
 414                 }
 415                 gen.emitJump(getLIRBlock((FixedNode) successors.first()));
 416             }
 417 
 418             assert verifyBlock(gen.getResult().getLIR(), block);
 419         }
 420     }
 421 
 422     @SuppressWarnings("try")
 423     protected void matchComplexExpressions(List<Node> nodes) {
 424         if (matchRules != null) {
 425             DebugContext debug = gen.getResult().getLIR().getDebug();
 426             try (DebugContext.Scope s = debug.scope("MatchComplexExpressions")) {
 427                 if (LogVerbose.getValue(nodeOperands.graph().getOptions())) {
 428                     int i = 0;
 429                     for (Node node : nodes) {
 430                         debug.log("%d: (%s) %1S", i++, node.getUsageCount(), node);
 431                     }
 432                 }
 433 
 434                 // Match the nodes in backwards order to encourage longer matches.
 435                 for (int index = nodes.size() - 1; index >= 0; index--) {
 436                     Node node = nodes.get(index);
 437                     if (getOperand(node) != null) {
 438                         continue;
 439                     }
 440                     // See if this node is the root of any MatchStatements
 441                     List<MatchStatement> statements = matchRules.get(node.getClass());
 442                     if (statements != null) {
 443                         for (MatchStatement statement : statements) {
 444                             if (statement.generate(this, index, node, nodes)) {
 445                                 // Found a match so skip to the next
 446                                 break;
 447                             }
 448                         }
 449                     }
 450                 }
 451             }
 452         }
 453     }
 454 
 455     protected abstract boolean peephole(ValueNode valueNode);
 456 
 457     private void doRoot(ValueNode instr) {
 458         if (traceLIRGeneratorLevel >= 2) {
 459             TTY.println("Emitting LIR for instruction " + instr);
 460         }
 461         currentInstruction = instr;
 462         DebugContext debug = instr.getDebug();
 463         debug.log("Visiting %s", instr);
 464         emitNode(instr);
 465         debug.log("Operand for %s = %s", instr, getOperand(instr));
 466     }
 467 
 468     protected void emitNode(ValueNode node) {
 469         if (node.getDebug().isLogEnabled() && node.stamp(NodeView.DEFAULT).isEmpty()) {
 470             node.getDebug().log("This node has an empty stamp, we are emitting dead code(?): %s", node);
 471         }
 472         if (node instanceof LIRLowerable) {
 473             ((LIRLowerable) node).generate(this);
 474         } else {
 475             throw GraalError.shouldNotReachHere("node is not LIRLowerable: " + node);
 476         }
 477     }
 478 
 479     protected void emitPrologue(StructuredGraph graph) {
 480         CallingConvention incomingArguments = gen.getResult().getCallingConvention();
 481 
 482         Value[] params = new Value[incomingArguments.getArgumentCount()];
 483         for (int i = 0; i < params.length; i++) {
 484             params[i] = incomingArguments.getArgument(i);
 485             if (ValueUtil.isStackSlot(params[i])) {
 486                 StackSlot slot = ValueUtil.asStackSlot(params[i]);
 487                 if (slot.isInCallerFrame() && !gen.getResult().getLIR().hasArgInCallerFrame()) {
 488                     gen.getResult().getLIR().setHasArgInCallerFrame();
 489                 }
 490             }
 491         }
 492 
 493         gen.emitIncomingValues(params);
 494 
 495         for (ParameterNode param : graph.getNodes(ParameterNode.TYPE)) {
 496             Value paramValue = params[param.index()];
 497             assert paramValue.getValueKind().equals(getLIRGeneratorTool().getLIRKind(param.stamp(NodeView.DEFAULT))) : paramValue + " " +
 498                             getLIRGeneratorTool().getLIRKind(param.stamp(NodeView.DEFAULT));
 499             setResult(param, gen.emitMove(paramValue));
 500         }
 501     }
 502 
 503     @Override
 504     public void visitMerge(AbstractMergeNode x) {
 505     }
 506 
 507     @Override
 508     public void visitEndNode(AbstractEndNode end) {
 509         AbstractMergeNode merge = end.merge();
 510         JumpOp jump = newJumpOp(getLIRBlock(merge));
 511         jump.setPhiValues(createPhiOut(merge, end));
 512         append(jump);
 513     }
 514 
 515     /**
 516      * Runtime specific classes can override this to insert a safepoint at the end of a loop.
 517      */
 518     @Override
 519     public void visitLoopEnd(LoopEndNode x) {
 520     }
 521 
 522     protected JumpOp newJumpOp(LabelRef ref) {
 523         return new JumpOp(ref);
 524     }
 525 
 526     protected LIRKind getPhiKind(PhiNode phi) {
 527         return gen.getLIRKind(phi.stamp(NodeView.DEFAULT));
 528     }
 529 
 530     @Override
 531     public void emitIf(IfNode x) {
 532         emitBranch(x.condition(), getLIRBlock(x.trueSuccessor()), getLIRBlock(x.falseSuccessor()), x.probability(x.trueSuccessor()));
 533     }
 534 
 535     public void emitBranch(LogicNode node, LabelRef trueSuccessor, LabelRef falseSuccessor, double trueSuccessorProbability) {
 536         if (node instanceof IsNullNode) {
 537             emitNullCheckBranch((IsNullNode) node, trueSuccessor, falseSuccessor, trueSuccessorProbability);
 538         } else if (node instanceof CompareNode) {
 539             emitCompareBranch((CompareNode) node, trueSuccessor, falseSuccessor, trueSuccessorProbability);
 540         } else if (node instanceof LogicConstantNode) {
 541             emitConstantBranch(((LogicConstantNode) node).getValue(), trueSuccessor, falseSuccessor);
 542         } else if (node instanceof IntegerTestNode) {
 543             emitIntegerTestBranch((IntegerTestNode) node, trueSuccessor, falseSuccessor, trueSuccessorProbability);
 544         } else {
 545             throw GraalError.unimplemented(node.toString());
 546         }
 547     }
 548 
 549     private void emitNullCheckBranch(IsNullNode node, LabelRef trueSuccessor, LabelRef falseSuccessor, double trueSuccessorProbability) {
 550         LIRKind kind = gen.getLIRKind(node.getValue().stamp(NodeView.DEFAULT));
 551         Value nullValue = gen.emitConstant(kind, node.nullConstant());
 552         gen.emitCompareBranch(kind.getPlatformKind(), operand(node.getValue()), nullValue, Condition.EQ, false, trueSuccessor, falseSuccessor, trueSuccessorProbability);
 553     }
 554 
 555     public void emitCompareBranch(CompareNode compare, LabelRef trueSuccessor, LabelRef falseSuccessor, double trueSuccessorProbability) {
 556         PlatformKind kind = gen.getLIRKind(compare.getX().stamp(NodeView.DEFAULT)).getPlatformKind();
 557         gen.emitCompareBranch(kind, operand(compare.getX()), operand(compare.getY()), compare.condition().asCondition(), compare.unorderedIsTrue(), trueSuccessor, falseSuccessor,
 558                         trueSuccessorProbability);
 559     }
 560 
 561     public void emitIntegerTestBranch(IntegerTestNode test, LabelRef trueSuccessor, LabelRef falseSuccessor, double trueSuccessorProbability) {
 562         gen.emitIntegerTestBranch(operand(test.getX()), operand(test.getY()), trueSuccessor, falseSuccessor, trueSuccessorProbability);
 563     }
 564 
 565     public void emitConstantBranch(boolean value, LabelRef trueSuccessorBlock, LabelRef falseSuccessorBlock) {
 566         LabelRef block = value ? trueSuccessorBlock : falseSuccessorBlock;
 567         gen.emitJump(block);
 568     }
 569 
 570     @Override
 571     public void emitConditional(ConditionalNode conditional) {
 572         Value tVal = operand(conditional.trueValue());
 573         Value fVal = operand(conditional.falseValue());
 574         setResult(conditional, emitConditional(conditional.condition(), tVal, fVal));
 575     }
 576 
 577     public Variable emitConditional(LogicNode node, Value trueValue, Value falseValue) {
 578         if (node instanceof IsNullNode) {
 579             IsNullNode isNullNode = (IsNullNode) node;
 580             LIRKind kind = gen.getLIRKind(isNullNode.getValue().stamp(NodeView.DEFAULT));
 581             Value nullValue = gen.emitConstant(kind, isNullNode.nullConstant());
 582             return gen.emitConditionalMove(kind.getPlatformKind(), operand(isNullNode.getValue()), nullValue, Condition.EQ, false, trueValue, falseValue);
 583         } else if (node instanceof CompareNode) {
 584             CompareNode compare = (CompareNode) node;
 585             PlatformKind kind = gen.getLIRKind(compare.getX().stamp(NodeView.DEFAULT)).getPlatformKind();
 586             return gen.emitConditionalMove(kind, operand(compare.getX()), operand(compare.getY()), compare.condition().asCondition(), compare.unorderedIsTrue(), trueValue, falseValue);
 587         } else if (node instanceof LogicConstantNode) {
 588             return gen.emitMove(((LogicConstantNode) node).getValue() ? trueValue : falseValue);
 589         } else if (node instanceof IntegerTestNode) {
 590             IntegerTestNode test = (IntegerTestNode) node;
 591             return gen.emitIntegerTestMove(operand(test.getX()), operand(test.getY()), trueValue, falseValue);
 592         } else {
 593             throw GraalError.unimplemented(node.toString());
 594         }
 595     }
 596 
 597     @Override
 598     public void emitInvoke(Invoke x) {
 599         LoweredCallTargetNode callTarget = (LoweredCallTargetNode) x.callTarget();
 600         FrameMapBuilder frameMapBuilder = gen.getResult().getFrameMapBuilder();
 601         CallingConvention invokeCc = frameMapBuilder.getRegisterConfig().getCallingConvention(callTarget.callType(), x.asNode().stamp(NodeView.DEFAULT).javaType(gen.getMetaAccess()),
 602                         callTarget.signature(), gen);
 603         frameMapBuilder.callsMethod(invokeCc);
 604 
 605         Value[] parameters = visitInvokeArguments(invokeCc, callTarget.arguments());
 606 
 607         LabelRef exceptionEdge = null;
 608         if (x instanceof InvokeWithExceptionNode) {
 609             exceptionEdge = getLIRBlock(((InvokeWithExceptionNode) x).exceptionEdge());
 610         }
 611         LIRFrameState callState = stateWithExceptionEdge(x, exceptionEdge);
 612 
 613         Value result = invokeCc.getReturn();
 614         if (callTarget instanceof DirectCallTargetNode) {
 615             emitDirectCall((DirectCallTargetNode) callTarget, result, parameters, AllocatableValue.NONE, callState);
 616         } else if (callTarget instanceof IndirectCallTargetNode) {
 617             emitIndirectCall((IndirectCallTargetNode) callTarget, result, parameters, AllocatableValue.NONE, callState);
 618         } else {
 619             throw GraalError.shouldNotReachHere();
 620         }
 621 
 622         if (isLegal(result)) {
 623             setResult(x.asNode(), gen.emitMove(result));
 624         }
 625 
 626         if (x instanceof InvokeWithExceptionNode) {
 627             gen.emitJump(getLIRBlock(((InvokeWithExceptionNode) x).next()));
 628         }
 629     }
 630 
 631     protected abstract void emitDirectCall(DirectCallTargetNode callTarget, Value result, Value[] parameters, Value[] temps, LIRFrameState callState);
 632 
 633     protected abstract void emitIndirectCall(IndirectCallTargetNode callTarget, Value result, Value[] parameters, Value[] temps, LIRFrameState callState);
 634 
 635     @Override
 636     public Value[] visitInvokeArguments(CallingConvention invokeCc, Collection<ValueNode> arguments) {
 637         // for each argument, load it into the correct location
 638         Value[] result = new Value[arguments.size()];
 639         int j = 0;
 640         for (ValueNode arg : arguments) {
 641             if (arg != null) {
 642                 AllocatableValue operand = invokeCc.getArgument(j);
 643                 gen.emitMove(operand, operand(arg));
 644                 result[j] = operand;
 645                 j++;
 646             } else {
 647                 throw GraalError.shouldNotReachHere("I thought we no longer have null entries for two-slot types...");
 648             }
 649         }
 650         return result;
 651     }
 652 
 653     /**
 654      * This method tries to create a switch implementation that is optimal for the given switch. It
 655      * will either generate a sequential if/then/else cascade, a set of range tests or a table
 656      * switch.
 657      *
 658      * If the given switch does not contain int keys, it will always create a sequential
 659      * implementation.
 660      */
 661     @Override
 662     public void emitSwitch(SwitchNode x) {
 663         assert x.defaultSuccessor() != null;
 664         LabelRef defaultTarget = getLIRBlock(x.defaultSuccessor());
 665         int keyCount = x.keyCount();
 666         if (keyCount == 0) {
 667             gen.emitJump(defaultTarget);
 668         } else {
 669             Variable value = gen.load(operand(x.value()));
 670             if (keyCount == 1) {
 671                 assert defaultTarget != null;
 672                 double probability = x.probability(x.keySuccessor(0));
 673                 LIRKind kind = gen.getLIRKind(x.value().stamp(NodeView.DEFAULT));
 674                 Value key = gen.emitConstant(kind, x.keyAt(0));
 675                 gen.emitCompareBranch(kind.getPlatformKind(), gen.load(operand(x.value())), key, Condition.EQ, false, getLIRBlock(x.keySuccessor(0)), defaultTarget, probability);
 676             } else if (x instanceof IntegerSwitchNode && x.isSorted()) {
 677                 IntegerSwitchNode intSwitch = (IntegerSwitchNode) x;
 678                 LabelRef[] keyTargets = new LabelRef[keyCount];
 679                 JavaConstant[] keyConstants = new JavaConstant[keyCount];
 680                 double[] keyProbabilities = new double[keyCount];
 681                 JavaKind keyKind = intSwitch.keyAt(0).getJavaKind();
 682                 for (int i = 0; i < keyCount; i++) {
 683                     keyTargets[i] = getLIRBlock(intSwitch.keySuccessor(i));
 684                     keyConstants[i] = intSwitch.keyAt(i);
 685                     keyProbabilities[i] = intSwitch.keyProbability(i);
 686                     assert keyConstants[i].getJavaKind() == keyKind;
 687                 }
 688                 gen.emitStrategySwitch(keyConstants, keyProbabilities, keyTargets, defaultTarget, value);
 689             } else {
 690                 // keyKind != JavaKind.Int || !x.isSorted()
 691                 LabelRef[] keyTargets = new LabelRef[keyCount];
 692                 Constant[] keyConstants = new Constant[keyCount];
 693                 double[] keyProbabilities = new double[keyCount];
 694                 for (int i = 0; i < keyCount; i++) {
 695                     keyTargets[i] = getLIRBlock(x.keySuccessor(i));
 696                     keyConstants[i] = x.keyAt(i);
 697                     keyProbabilities[i] = x.keyProbability(i);
 698                 }
 699 
 700                 // hopefully only a few entries
 701                 gen.emitStrategySwitch(new SwitchStrategy.SequentialStrategy(keyProbabilities, keyConstants), value, keyTargets, defaultTarget);
 702             }
 703         }
 704     }
 705 
 706     public DebugInfoBuilder getDebugInfoBuilder() {
 707         assert debugInfoBuilder != null;
 708         return debugInfoBuilder;
 709     }
 710 
 711     private static FrameState getFrameState(DeoptimizingNode deopt) {
 712         if (deopt instanceof DeoptimizingNode.DeoptBefore) {
 713             assert !(deopt instanceof DeoptimizingNode.DeoptDuring || deopt instanceof DeoptimizingNode.DeoptAfter);
 714             return ((DeoptimizingNode.DeoptBefore) deopt).stateBefore();
 715         } else if (deopt instanceof DeoptimizingNode.DeoptDuring) {
 716             assert !(deopt instanceof DeoptimizingNode.DeoptAfter);
 717             return ((DeoptimizingNode.DeoptDuring) deopt).stateDuring();
 718         } else {
 719             assert deopt instanceof DeoptimizingNode.DeoptAfter;
 720             return ((DeoptimizingNode.DeoptAfter) deopt).stateAfter();
 721         }
 722     }
 723 
 724     @Override
 725     public LIRFrameState state(DeoptimizingNode deopt) {
 726         if (!deopt.canDeoptimize()) {
 727             return null;
 728         }
 729         return stateFor(getFrameState(deopt));
 730     }
 731 
 732     public LIRFrameState stateWithExceptionEdge(DeoptimizingNode deopt, LabelRef exceptionEdge) {
 733         if (!deopt.canDeoptimize()) {
 734             return null;
 735         }
 736         return stateForWithExceptionEdge(getFrameState(deopt), exceptionEdge);
 737     }
 738 
 739     public LIRFrameState stateFor(FrameState state) {
 740         return stateForWithExceptionEdge(state, null);
 741     }
 742 
 743     public LIRFrameState stateForWithExceptionEdge(FrameState state, LabelRef exceptionEdge) {
 744         if (gen.needOnlyOopMaps()) {
 745             return new LIRFrameState(null, null, null);
 746         }
 747         assert state != null;
 748         return getDebugInfoBuilder().build(state, exceptionEdge);
 749     }
 750 
 751     @Override
 752     public void emitOverflowCheckBranch(AbstractBeginNode overflowSuccessor, AbstractBeginNode next, Stamp stamp, double probability) {
 753         LIRKind cmpKind = getLIRGeneratorTool().getLIRKind(stamp);
 754         gen.emitOverflowCheckBranch(getLIRBlock(overflowSuccessor), getLIRBlock(next), cmpKind, probability);
 755     }
 756 
 757     @Override
 758     public void visitFullInfopointNode(FullInfopointNode i) {
 759         append(new FullInfopointOp(stateFor(i.getState()), i.getReason()));
 760     }
 761 
 762     @Override
 763     public void setSourcePosition(NodeSourcePosition position) {
 764         gen.setSourcePosition(position);
 765     }
 766 
 767     @Override
 768     public LIRGeneratorTool getLIRGeneratorTool() {
 769         return gen;
 770     }
 771 
 772     @Override
 773     public void emitReadExceptionObject(ValueNode node) {
 774         LIRGeneratorTool lirGenTool = getLIRGeneratorTool();
 775         Value returnRegister = lirGenTool.getRegisterConfig().getReturnRegister(node.getStackKind()).asValue(
 776                         LIRKind.fromJavaKind(lirGenTool.target().arch, node.getStackKind()));
 777         lirGenTool.emitIncomingValues(new Value[]{returnRegister});
 778         setResult(node, lirGenTool.emitMove(returnRegister));
 779     }
 780 }