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