001/*
002 * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.lir.gen;
024
025import static com.oracle.graal.lir.LIRValueUtil.*;
026import static jdk.internal.jvmci.code.ValueUtil.*;
027
028import java.util.*;
029
030import jdk.internal.jvmci.code.*;
031import jdk.internal.jvmci.common.*;
032import jdk.internal.jvmci.meta.*;
033import jdk.internal.jvmci.options.*;
034
035import com.oracle.graal.asm.*;
036import com.oracle.graal.compiler.common.calc.*;
037import com.oracle.graal.compiler.common.cfg.*;
038import com.oracle.graal.compiler.common.spi.*;
039import com.oracle.graal.compiler.common.type.*;
040import com.oracle.graal.debug.*;
041import com.oracle.graal.lir.*;
042import com.oracle.graal.lir.StandardOp.BlockEndOp;
043import com.oracle.graal.lir.StandardOp.LabelOp;
044
045/**
046 * This class traverses the HIR instructions and generates LIR instructions from them.
047 */
048public abstract class LIRGenerator implements LIRGeneratorTool {
049
050    public static class Options {
051        // @formatter:off
052        @Option(help = "Print HIR along side LIR as the latter is generated", type = OptionType.Debug)
053        public static final OptionValue<Boolean> PrintIRWithLIR = new OptionValue<>(false);
054        @Option(help = "The trace level for the LIR generator", type = OptionType.Debug)
055        public static final OptionValue<Integer> TraceLIRGeneratorLevel = new OptionValue<>(0);
056        // @formatter:on
057    }
058
059    private final LIRKindTool lirKindTool;
060
061    private final CodeGenProviders providers;
062    private final CallingConvention cc;
063
064    private AbstractBlockBase<?> currentBlock;
065
066    private LIRGenerationResult res;
067
068    public LIRGenerator(LIRKindTool lirKindTool, CodeGenProviders providers, CallingConvention cc, LIRGenerationResult res) {
069        this.lirKindTool = lirKindTool;
070        this.res = res;
071        this.providers = providers;
072        this.cc = cc;
073    }
074
075    @Override
076    public TargetDescription target() {
077        return getCodeCache().getTarget();
078    }
079
080    public CodeGenProviders getProviders() {
081        return providers;
082    }
083
084    @Override
085    public MetaAccessProvider getMetaAccess() {
086        return providers.getMetaAccess();
087    }
088
089    @Override
090    public CodeCacheProvider getCodeCache() {
091        return providers.getCodeCache();
092    }
093
094    @Override
095    public ForeignCallsProvider getForeignCalls() {
096        return providers.getForeignCalls();
097    }
098
099    protected LIRKindTool getLIRKindTool() {
100        return lirKindTool;
101    }
102
103    @Override
104    public Variable newVariable(LIRKind lirKind) {
105        return new Variable(lirKind, res.getLIR().nextVariable());
106    }
107
108    @Override
109    public RegisterAttributes attributes(Register register) {
110        return res.getFrameMapBuilder().getRegisterConfig().getAttributesMap()[register.number];
111    }
112
113    @Override
114    public Variable emitMove(Value input) {
115        assert !(input instanceof Variable) : "Creating a copy of a variable via this method is not supported (and potentially a bug): " + input;
116        Variable result = newVariable(input.getLIRKind());
117        emitMove(result, input);
118        return result;
119    }
120
121    @Override
122    public Value emitLoadConstant(LIRKind kind, Constant constant) {
123        JavaConstant javaConstant = (JavaConstant) constant;
124        if (canInlineConstant(javaConstant)) {
125            return javaConstant;
126        } else {
127            return emitMove(javaConstant);
128        }
129    }
130
131    public AllocatableValue asAllocatable(Value value) {
132        if (isAllocatableValue(value)) {
133            return asAllocatableValue(value);
134        } else {
135            return emitMove(value);
136        }
137    }
138
139    public Variable load(Value value) {
140        if (!isVariable(value)) {
141            return emitMove(value);
142        }
143        return (Variable) value;
144    }
145
146    /**
147     * Checks whether the supplied constant can be used without loading it into a register for most
148     * operations, i.e., for commonly used arithmetic, logical, and comparison operations.
149     *
150     * @param c The constant to check.
151     * @return True if the constant can be used directly, false if the constant needs to be in a
152     *         register.
153     */
154    protected abstract boolean canInlineConstant(JavaConstant c);
155
156    public Value loadNonConst(Value value) {
157        if (isConstant(value) && !canInlineConstant((JavaConstant) value)) {
158            return emitMove(value);
159        }
160        return value;
161    }
162
163    /**
164     * Determines if only oop maps are required for the code generated from the LIR.
165     */
166    public boolean needOnlyOopMaps() {
167        return false;
168    }
169
170    /**
171     * Gets the ABI specific operand used to return a value of a given kind from a method.
172     *
173     * @param kind the kind of value being returned
174     * @return the operand representing the ABI defined location used return a value of kind
175     *         {@code kind}
176     */
177    public AllocatableValue resultOperandFor(LIRKind kind) {
178        return res.getFrameMapBuilder().getRegisterConfig().getReturnRegister((Kind) kind.getPlatformKind()).asValue(kind);
179    }
180
181    public <I extends LIRInstruction> I append(I op) {
182        if (Options.PrintIRWithLIR.getValue() && !TTY.isSuppressed()) {
183            TTY.println(op.toStringWithIdPrefix());
184            TTY.println();
185        }
186        assert LIRVerifier.verify(op);
187        res.getLIR().getLIRforBlock(getCurrentBlock()).add(op);
188        return op;
189    }
190
191    public boolean hasBlockEnd(AbstractBlockBase<?> block) {
192        List<LIRInstruction> ops = getResult().getLIR().getLIRforBlock(block);
193        if (ops.size() == 0) {
194            return false;
195        }
196        return ops.get(ops.size() - 1) instanceof BlockEndOp;
197    }
198
199    private final class BlockScopeImpl extends BlockScope {
200
201        private BlockScopeImpl(AbstractBlockBase<?> block) {
202            currentBlock = block;
203        }
204
205        private void doBlockStart() {
206            if (Options.PrintIRWithLIR.getValue()) {
207                TTY.print(currentBlock.toString());
208            }
209
210            // set up the list of LIR instructions
211            assert res.getLIR().getLIRforBlock(currentBlock) == null : "LIR list already computed for this block";
212            res.getLIR().setLIRforBlock(currentBlock, new ArrayList<LIRInstruction>());
213
214            append(new LabelOp(new Label(currentBlock.getId()), currentBlock.isAligned()));
215
216            if (Options.TraceLIRGeneratorLevel.getValue() >= 1) {
217                TTY.println("BEGIN Generating LIR for block B" + currentBlock.getId());
218            }
219        }
220
221        private void doBlockEnd() {
222            if (Options.TraceLIRGeneratorLevel.getValue() >= 1) {
223                TTY.println("END Generating LIR for block B" + currentBlock.getId());
224            }
225
226            if (Options.PrintIRWithLIR.getValue()) {
227                TTY.println();
228            }
229            currentBlock = null;
230        }
231
232        @Override
233        public AbstractBlockBase<?> getCurrentBlock() {
234            return currentBlock;
235        }
236
237        @Override
238        public void close() {
239            doBlockEnd();
240        }
241
242    }
243
244    public final BlockScope getBlockScope(AbstractBlockBase<?> block) {
245        BlockScopeImpl blockScope = new BlockScopeImpl(block);
246        blockScope.doBlockStart();
247        return blockScope;
248    }
249
250    public void emitIncomingValues(Value[] params) {
251        ((LabelOp) res.getLIR().getLIRforBlock(getCurrentBlock()).get(0)).setIncomingValues(params);
252    }
253
254    public abstract void emitJump(LabelRef label);
255
256    public abstract void emitCompareBranch(PlatformKind cmpKind, Value left, Value right, Condition cond, boolean unorderedIsTrue, LabelRef trueDestination, LabelRef falseDestination,
257                    double trueDestinationProbability);
258
259    public abstract void emitOverflowCheckBranch(LabelRef overflow, LabelRef noOverflow, LIRKind cmpKind, double overflowProbability);
260
261    public abstract void emitIntegerTestBranch(Value left, Value right, LabelRef trueDestination, LabelRef falseDestination, double trueSuccessorProbability);
262
263    public abstract Variable emitConditionalMove(PlatformKind cmpKind, Value leftVal, Value right, Condition cond, boolean unorderedIsTrue, Value trueValue, Value falseValue);
264
265    public abstract Variable emitIntegerTestMove(Value leftVal, Value right, Value trueValue, Value falseValue);
266
267    /**
268     * Emits the single call operation at the heart of generating LIR for a
269     * {@linkplain #emitForeignCall(ForeignCallLinkage, LIRFrameState, Value...) foreign call}.
270     */
271    protected abstract void emitForeignCallOp(ForeignCallLinkage linkage, Value result, Value[] arguments, Value[] temps, LIRFrameState info);
272
273    public static AllocatableValue toStackKind(AllocatableValue value) {
274        if (value.getKind().getStackKind() != value.getKind()) {
275            // We only have stack-kinds in the LIR, so convert the operand kind for values from the
276            // calling convention.
277            LIRKind stackKind = value.getLIRKind().changeType(value.getKind().getStackKind());
278            if (isRegister(value)) {
279                return asRegister(value).asValue(stackKind);
280            } else if (isStackSlot(value)) {
281                return StackSlot.get(stackKind, asStackSlot(value).getRawOffset(), asStackSlot(value).getRawAddFrameSize());
282            } else {
283                throw JVMCIError.shouldNotReachHere();
284            }
285        }
286        return value;
287    }
288
289    @Override
290    public Variable emitForeignCall(ForeignCallLinkage linkage, LIRFrameState frameState, Value... args) {
291        LIRFrameState state = null;
292        if (linkage.needsDebugInfo()) {
293            if (frameState != null) {
294                state = frameState;
295            } else {
296                assert needOnlyOopMaps();
297                state = new LIRFrameState(null, null, null);
298            }
299        }
300
301        // move the arguments into the correct location
302        CallingConvention linkageCc = linkage.getOutgoingCallingConvention();
303        res.getFrameMapBuilder().callsMethod(linkageCc);
304        assert linkageCc.getArgumentCount() == args.length : "argument count mismatch";
305        Value[] argLocations = new Value[args.length];
306        for (int i = 0; i < args.length; i++) {
307            Value arg = args[i];
308            AllocatableValue loc = linkageCc.getArgument(i);
309            emitMove(loc, arg);
310            argLocations[i] = loc;
311        }
312        res.setForeignCall(true);
313        emitForeignCallOp(linkage, linkageCc.getReturn(), argLocations, linkage.getTemporaries(), state);
314
315        if (isLegal(linkageCc.getReturn())) {
316            return emitMove(linkageCc.getReturn());
317        } else {
318            return null;
319        }
320    }
321
322    public void emitStrategySwitch(JavaConstant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) {
323        int keyCount = keyConstants.length;
324        SwitchStrategy strategy = SwitchStrategy.getBestStrategy(keyProbabilities, keyConstants, keyTargets);
325        long valueRange = keyConstants[keyCount - 1].asLong() - keyConstants[0].asLong() + 1;
326        double tableSwitchDensity = keyCount / (double) valueRange;
327        /*
328         * This heuristic tries to find a compromise between the effort for the best switch strategy
329         * and the density of a tableswitch. If the effort for the strategy is at least 4, then a
330         * tableswitch is preferred if better than a certain value that starts at 0.5 and lowers
331         * gradually with additional effort.
332         */
333        if (strategy.getAverageEffort() < 4 || tableSwitchDensity < (1 / Math.sqrt(strategy.getAverageEffort()))) {
334            emitStrategySwitch(strategy, value, keyTargets, defaultTarget);
335        } else {
336            int minValue = keyConstants[0].asInt();
337            assert valueRange < Integer.MAX_VALUE;
338            LabelRef[] targets = new LabelRef[(int) valueRange];
339            for (int i = 0; i < valueRange; i++) {
340                targets[i] = defaultTarget;
341            }
342            for (int i = 0; i < keyCount; i++) {
343                targets[keyConstants[i].asInt() - minValue] = keyTargets[i];
344            }
345            emitTableSwitch(minValue, defaultTarget, targets, value);
346        }
347    }
348
349    public abstract void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget);
350
351    protected abstract void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key);
352
353    public CallingConvention getCallingConvention() {
354        return cc;
355    }
356
357    @Override
358    public void beforeRegisterAllocation() {
359    }
360
361    /**
362     * Gets a garbage value for a given kind.
363     */
364    protected JavaConstant zapValueForKind(PlatformKind kind) {
365        long dead = 0xDEADDEADDEADDEADL;
366        switch ((Kind) kind) {
367            case Boolean:
368                return JavaConstant.FALSE;
369            case Byte:
370                return JavaConstant.forByte((byte) dead);
371            case Char:
372                return JavaConstant.forChar((char) dead);
373            case Short:
374                return JavaConstant.forShort((short) dead);
375            case Int:
376                return JavaConstant.forInt((int) dead);
377            case Double:
378                return JavaConstant.forDouble(Double.longBitsToDouble(dead));
379            case Float:
380                return JavaConstant.forFloat(Float.intBitsToFloat((int) dead));
381            case Long:
382                return JavaConstant.forLong(dead);
383            case Object:
384                return JavaConstant.NULL_POINTER;
385            default:
386                throw new IllegalArgumentException(kind.toString());
387        }
388    }
389
390    public LIRKind getLIRKind(Stamp stamp) {
391        return stamp.getLIRKind(lirKindTool);
392    }
393
394    protected LIRKind getAddressKind(Value base, long displacement, Value index) {
395        if (base.getLIRKind().isValue() && (index.equals(Value.ILLEGAL) || index.getLIRKind().isValue())) {
396            return LIRKind.value(target().wordKind);
397        } else if (base.getLIRKind().isReference(0) && displacement == 0L && index.equals(Value.ILLEGAL)) {
398            return LIRKind.reference(target().wordKind);
399        } else {
400            return LIRKind.unknownReference(target().wordKind);
401        }
402    }
403
404    public AbstractBlockBase<?> getCurrentBlock() {
405        return currentBlock;
406    }
407
408    public LIRGenerationResult getResult() {
409        return res;
410    }
411
412    public void emitBlackhole(Value operand) {
413        append(new StandardOp.BlackholeOp(operand));
414    }
415
416    public LIRInstruction createBenchmarkCounter(String name, String group, Value increment) {
417        throw JVMCIError.unimplemented();
418    }
419
420    public LIRInstruction createMultiBenchmarkCounter(String[] names, String[] groups, Value[] increments) {
421        throw JVMCIError.unimplemented();
422    }
423
424    // automatic derived reference handling
425
426    protected abstract Variable emitAdd(LIRKind resultKind, Value a, Value b, boolean setFlags);
427
428    public final Variable emitAdd(Value aVal, Value bVal, boolean setFlags) {
429        LIRKind resultKind;
430        Value a = aVal;
431        Value b = bVal;
432
433        if (a.getKind().isNumericInteger()) {
434            LIRKind aKind = a.getLIRKind();
435            LIRKind bKind = b.getLIRKind();
436            assert a.getPlatformKind() == b.getPlatformKind();
437
438            if (aKind.isUnknownReference()) {
439                resultKind = aKind;
440            } else if (bKind.isUnknownReference()) {
441                resultKind = bKind;
442            } else if (aKind.isValue() && bKind.isValue()) {
443                resultKind = aKind;
444            } else if (aKind.isValue()) {
445                if (bKind.isDerivedReference()) {
446                    resultKind = bKind;
447                } else {
448                    AllocatableValue allocatable = asAllocatable(b);
449                    resultKind = bKind.makeDerivedReference(allocatable);
450                    b = allocatable;
451                }
452            } else if (bKind.isValue()) {
453                if (aKind.isDerivedReference()) {
454                    resultKind = aKind;
455                } else {
456                    AllocatableValue allocatable = asAllocatable(a);
457                    resultKind = aKind.makeDerivedReference(allocatable);
458                    a = allocatable;
459                }
460            } else {
461                resultKind = aKind.makeUnknownReference();
462            }
463        } else {
464            resultKind = LIRKind.combine(a, b);
465        }
466
467        return emitAdd(resultKind, a, b, setFlags);
468    }
469
470    protected abstract Variable emitSub(LIRKind resultKind, Value a, Value b, boolean setFlags);
471
472    public final Variable emitSub(Value aVal, Value bVal, boolean setFlags) {
473        LIRKind resultKind;
474        Value a = aVal;
475        Value b = bVal;
476
477        if (a.getKind().isNumericInteger()) {
478            LIRKind aKind = a.getLIRKind();
479            LIRKind bKind = b.getLIRKind();
480            assert a.getPlatformKind() == b.getPlatformKind();
481
482            if (aKind.isUnknownReference()) {
483                resultKind = aKind;
484            } else if (bKind.isUnknownReference()) {
485                resultKind = bKind;
486            }
487
488            if (aKind.isValue() && bKind.isValue()) {
489                resultKind = aKind;
490            } else if (bKind.isValue()) {
491                if (aKind.isDerivedReference()) {
492                    resultKind = aKind;
493                } else {
494                    AllocatableValue allocatable = asAllocatable(a);
495                    resultKind = aKind.makeDerivedReference(allocatable);
496                    a = allocatable;
497                }
498            } else if (aKind.isDerivedReference() && bKind.isDerivedReference() && aKind.getDerivedReferenceBase().equals(bKind.getDerivedReferenceBase())) {
499                resultKind = LIRKind.value(a.getPlatformKind());
500            } else {
501                resultKind = aKind.makeUnknownReference();
502            }
503        } else {
504            resultKind = LIRKind.combine(a, b);
505        }
506
507        return emitSub(resultKind, a, b, setFlags);
508    }
509}