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