1 /*
   2  * Copyright (c) 2013, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.lir.aarch64;
  26 
  27 import static jdk.vm.ci.code.ValueUtil.asAllocatableValue;
  28 import static jdk.vm.ci.code.ValueUtil.asRegister;
  29 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.HINT;
  30 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.REG;
  31 
  32 import java.util.function.Function;
  33 
  34 import jdk.vm.ci.meta.AllocatableValue;
  35 import org.graalvm.compiler.asm.Label;
  36 import org.graalvm.compiler.core.common.NumUtil;
  37 import org.graalvm.compiler.asm.aarch64.AArch64Assembler;
  38 import org.graalvm.compiler.asm.aarch64.AArch64Assembler.ConditionFlag;
  39 import org.graalvm.compiler.asm.aarch64.AArch64Assembler.ExtendType;
  40 import org.graalvm.compiler.asm.aarch64.AArch64MacroAssembler;
  41 import org.graalvm.compiler.code.CompilationResult.JumpTable;
  42 import org.graalvm.compiler.core.common.LIRKind;
  43 import org.graalvm.compiler.core.common.calc.Condition;
  44 import org.graalvm.compiler.debug.GraalError;
  45 import org.graalvm.compiler.lir.ConstantValue;
  46 import org.graalvm.compiler.lir.LIRInstructionClass;
  47 import org.graalvm.compiler.lir.LabelRef;
  48 import org.graalvm.compiler.lir.Opcode;
  49 import org.graalvm.compiler.lir.StandardOp;
  50 import org.graalvm.compiler.lir.SwitchStrategy;
  51 import org.graalvm.compiler.lir.SwitchStrategy.BaseSwitchClosure;
  52 import org.graalvm.compiler.lir.Variable;
  53 import org.graalvm.compiler.lir.asm.CompilationResultBuilder;
  54 
  55 import jdk.vm.ci.aarch64.AArch64Kind;
  56 import jdk.vm.ci.code.Register;
  57 import jdk.vm.ci.meta.Constant;
  58 import jdk.vm.ci.meta.JavaConstant;
  59 import jdk.vm.ci.meta.Value;
  60 
  61 public class AArch64ControlFlow {
  62 
  63     public abstract static class AbstractBranchOp extends AArch64BlockEndOp implements StandardOp.BranchOp {
  64         private final LabelRef trueDestination;
  65         private final LabelRef falseDestination;
  66 
  67         private final double trueDestinationProbability;
  68 
  69         private AbstractBranchOp(LIRInstructionClass<? extends AbstractBranchOp> c, LabelRef trueDestination, LabelRef falseDestination, double trueDestinationProbability) {
  70             super(c);
  71             this.trueDestination = trueDestination;
  72             this.falseDestination = falseDestination;
  73             this.trueDestinationProbability = trueDestinationProbability;
  74         }
  75 
  76         protected abstract void emitBranch(CompilationResultBuilder crb, AArch64MacroAssembler masm, LabelRef target, boolean negate);
  77 
  78         @Override
  79         public void emitCode(CompilationResultBuilder crb, AArch64MacroAssembler masm) {
  80             /*
  81              * Explanation: Depending on what the successor edge is, we can use the fall-through to
  82              * optimize the generated code. If neither is a successor edge, use the branch
  83              * probability to try to take the conditional jump as often as possible to avoid
  84              * executing two instructions instead of one.
  85              */
  86             if (crb.isSuccessorEdge(trueDestination)) {
  87                 emitBranch(crb, masm, falseDestination, true);
  88             } else if (crb.isSuccessorEdge(falseDestination)) {
  89                 emitBranch(crb, masm, trueDestination, false);
  90             } else if (trueDestinationProbability < 0.5) {
  91                 emitBranch(crb, masm, falseDestination, true);
  92                 masm.jmp(trueDestination.label());
  93             } else {
  94                 emitBranch(crb, masm, trueDestination, false);
  95                 masm.jmp(falseDestination.label());
  96             }
  97         }
  98     }
  99 
 100     public static class BranchOp extends AbstractBranchOp implements StandardOp.BranchOp {
 101         public static final LIRInstructionClass<BranchOp> TYPE = LIRInstructionClass.create(BranchOp.class);
 102 
 103         private final AArch64Assembler.ConditionFlag condition;
 104 
 105         public BranchOp(AArch64Assembler.ConditionFlag condition, LabelRef trueDestination, LabelRef falseDestination, double trueDestinationProbability) {
 106             super(TYPE, trueDestination, falseDestination, trueDestinationProbability);
 107             this.condition = condition;
 108         }
 109 
 110         @Override
 111         protected void emitBranch(CompilationResultBuilder crb, AArch64MacroAssembler masm, LabelRef target, boolean negate) {
 112             AArch64Assembler.ConditionFlag finalCond = negate ? condition.negate() : condition;
 113             masm.branchConditionally(finalCond, target.label());
 114         }
 115     }
 116 
 117     public static class CompareBranchZeroOp extends AbstractBranchOp implements StandardOp.BranchOp {
 118         public static final LIRInstructionClass<CompareBranchZeroOp> TYPE = LIRInstructionClass.create(CompareBranchZeroOp.class);
 119 
 120         @Use(REG) private AllocatableValue value;
 121 
 122         public CompareBranchZeroOp(AllocatableValue value, LabelRef trueDestination, LabelRef falseDestination, double trueDestinationProbability) {
 123             super(TYPE, trueDestination, falseDestination, trueDestinationProbability);
 124             this.value = value;
 125         }
 126 
 127         @Override
 128         protected void emitBranch(CompilationResultBuilder crb, AArch64MacroAssembler masm, LabelRef target, boolean negate) {
 129             AArch64Kind kind = (AArch64Kind) this.value.getPlatformKind();
 130             assert kind.isInteger();
 131             int size = kind.getSizeInBytes() * Byte.SIZE;
 132 
 133             if (negate) {
 134                 masm.cbnz(size, asRegister(this.value), target.label());
 135             } else {
 136                 masm.cbz(size, asRegister(this.value), target.label());
 137             }
 138         }
 139     }
 140 
 141     public static class BitTestAndBranchOp extends AbstractBranchOp implements StandardOp.BranchOp {
 142         public static final LIRInstructionClass<BitTestAndBranchOp> TYPE = LIRInstructionClass.create(BitTestAndBranchOp.class);
 143 
 144         @Use protected AllocatableValue value;
 145         private final int index;
 146 
 147         public BitTestAndBranchOp(LabelRef trueDestination, LabelRef falseDestination, AllocatableValue value, double trueDestinationProbability, int index) {
 148             super(TYPE, trueDestination, falseDestination, trueDestinationProbability);
 149             this.value = value;
 150             this.index = index;
 151         }
 152 
 153         @Override
 154         protected void emitBranch(CompilationResultBuilder crb, AArch64MacroAssembler masm, LabelRef target, boolean negate) {
 155             ConditionFlag cond = negate ? ConditionFlag.NE : ConditionFlag.EQ;
 156             Label label = target.label();
 157             boolean isFarBranch;
 158 
 159             if (label.isBound()) {
 160                 isFarBranch = NumUtil.isSignedNbit(18, masm.position() - label.position());
 161             } else {
 162                 // Max range of tbz is +-2^13 instructions. We estimate that each LIR instruction
 163                 // emits 2 AArch64 instructions on average. Thus we test for maximum 2^12 LIR
 164                 // instruction offset.
 165                 int maxLIRDistance = (1 << 12);
 166                 isFarBranch = !crb.labelWithinRange(this, label, maxLIRDistance);
 167             }
 168 
 169             if (isFarBranch) {
 170                 cond = cond.negate();
 171                 label = new Label();
 172             }
 173 
 174             if (cond == ConditionFlag.EQ) {
 175                 masm.tbz(asRegister(value), index, label);
 176             } else {
 177                 masm.tbnz(asRegister(value), index, label);
 178             }
 179 
 180             if (isFarBranch) {
 181                 masm.jmp(target.label());
 182                 masm.bind(label);
 183             }
 184         }
 185     }
 186 
 187     @Opcode("CMOVE")
 188     public static class CondMoveOp extends AArch64LIRInstruction {
 189         public static final LIRInstructionClass<CondMoveOp> TYPE = LIRInstructionClass.create(CondMoveOp.class);
 190 
 191         @Def protected Value result;
 192         @Use protected Value trueValue;
 193         @Use protected Value falseValue;
 194         private final AArch64Assembler.ConditionFlag condition;
 195 
 196         public CondMoveOp(Variable result, AArch64Assembler.ConditionFlag condition, Value trueValue, Value falseValue) {
 197             super(TYPE);
 198             assert trueValue.getPlatformKind() == falseValue.getPlatformKind() && trueValue.getPlatformKind() == result.getPlatformKind();
 199             this.result = result;
 200             this.condition = condition;
 201             this.trueValue = trueValue;
 202             this.falseValue = falseValue;
 203         }
 204 
 205         @Override
 206         public void emitCode(CompilationResultBuilder crb, AArch64MacroAssembler masm) {
 207             AArch64Kind kind = (AArch64Kind) trueValue.getPlatformKind();
 208             int size = kind.getSizeInBytes() * Byte.SIZE;
 209             if (kind.isInteger()) {
 210                 masm.cmov(size, asRegister(result), asRegister(trueValue), asRegister(falseValue), condition);
 211             } else {
 212                 masm.fcmov(size, asRegister(result), asRegister(trueValue), asRegister(falseValue), condition);
 213             }
 214         }
 215     }
 216 
 217     public static class CondSetOp extends AArch64LIRInstruction {
 218         public static final LIRInstructionClass<CondSetOp> TYPE = LIRInstructionClass.create(CondSetOp.class);
 219 
 220         @Def protected Value result;
 221         private final AArch64Assembler.ConditionFlag condition;
 222 
 223         public CondSetOp(Variable result, AArch64Assembler.ConditionFlag condition) {
 224             super(TYPE);
 225             this.result = result;
 226             this.condition = condition;
 227         }
 228 
 229         @Override
 230         public void emitCode(CompilationResultBuilder crb, AArch64MacroAssembler masm) {
 231             int size = result.getPlatformKind().getSizeInBytes() * Byte.SIZE;
 232             masm.cset(size, asRegister(result), condition);
 233         }
 234     }
 235 
 236     public static class StrategySwitchOp extends AArch64BlockEndOp implements StandardOp.BlockEndOp {
 237         public static final LIRInstructionClass<StrategySwitchOp> TYPE = LIRInstructionClass.create(StrategySwitchOp.class);
 238 
 239         private final Constant[] keyConstants;
 240         protected final SwitchStrategy strategy;
 241         private final Function<Condition, ConditionFlag> converter;
 242         private final LabelRef[] keyTargets;
 243         private final LabelRef defaultTarget;
 244         @Alive protected Value key;
 245         // TODO (das) This could be optimized: We only need the scratch register in case of a
 246         // datapatch, or too large immediates.
 247         @Temp protected Value scratch;
 248 
 249         public StrategySwitchOp(SwitchStrategy strategy, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch,
 250                         Function<Condition, ConditionFlag> converter) {
 251             this(TYPE, strategy, keyTargets, defaultTarget, key, scratch, converter);
 252         }
 253 
 254         protected StrategySwitchOp(LIRInstructionClass<? extends StrategySwitchOp> c, SwitchStrategy strategy, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch,
 255                         Function<Condition, ConditionFlag> converter) {
 256             super(c);
 257             this.strategy = strategy;
 258             this.converter = converter;
 259             this.keyConstants = strategy.getKeyConstants();
 260             this.keyTargets = keyTargets;
 261             this.defaultTarget = defaultTarget;
 262             this.key = key;
 263             this.scratch = scratch;
 264             assert keyConstants.length == keyTargets.length;
 265             assert keyConstants.length == strategy.keyProbabilities.length;
 266         }
 267 
 268         @Override
 269         public void emitCode(CompilationResultBuilder crb, AArch64MacroAssembler masm) {
 270             strategy.run(new SwitchClosure(asRegister(key), crb, masm));
 271         }
 272 
 273         public class SwitchClosure extends BaseSwitchClosure {
 274 
 275             protected final Register keyRegister;
 276             protected final CompilationResultBuilder crb;
 277             protected final AArch64MacroAssembler masm;
 278 
 279             protected SwitchClosure(Register keyRegister, CompilationResultBuilder crb, AArch64MacroAssembler masm) {
 280                 super(crb, masm, keyTargets, defaultTarget);
 281                 this.keyRegister = keyRegister;
 282                 this.crb = crb;
 283                 this.masm = masm;
 284             }
 285 
 286             protected void emitComparison(Constant c) {
 287                 JavaConstant jc = (JavaConstant) c;
 288                 ConstantValue constVal = new ConstantValue(LIRKind.value(key.getPlatformKind()), c);
 289                 switch (jc.getJavaKind()) {
 290                     case Int:
 291                         long lc = jc.asLong();
 292                         assert NumUtil.isInt(lc);
 293                         emitCompare(crb, masm, key, scratch, constVal);
 294                         break;
 295                     case Long:
 296                         emitCompare(crb, masm, key, scratch, constVal);
 297                         break;
 298                     case Object:
 299                         emitCompare(crb, masm, key, scratch, constVal);
 300                         break;
 301                     default:
 302                         throw new GraalError("switch only supported for int, long and object");
 303                 }
 304             }
 305 
 306             @Override
 307             protected void conditionalJump(int index, Condition condition, Label target) {
 308                 emitComparison(keyConstants[index]);
 309                 masm.branchConditionally(converter.apply(condition), target);
 310             }
 311         }
 312     }
 313 
 314     public static final class TableSwitchOp extends AArch64BlockEndOp {
 315         public static final LIRInstructionClass<TableSwitchOp> TYPE = LIRInstructionClass.create(TableSwitchOp.class);
 316         private final int lowKey;
 317         private final LabelRef defaultTarget;
 318         private final LabelRef[] targets;
 319         @Use protected Value index;
 320         @Temp({REG, HINT}) protected Value idxScratch;
 321         @Temp protected Value scratch;
 322 
 323         public TableSwitchOp(final int lowKey, final LabelRef defaultTarget, final LabelRef[] targets, Value index, Variable scratch, Variable idxScratch) {
 324             super(TYPE);
 325             this.lowKey = lowKey;
 326             this.defaultTarget = defaultTarget;
 327             this.targets = targets;
 328             this.index = index;
 329             this.scratch = scratch;
 330             this.idxScratch = idxScratch;
 331         }
 332 
 333         @Override
 334         public void emitCode(CompilationResultBuilder crb, AArch64MacroAssembler masm) {
 335             Register indexReg = asRegister(index, AArch64Kind.DWORD);
 336             Register idxScratchReg = asRegister(idxScratch, AArch64Kind.DWORD);
 337             Register scratchReg = asRegister(scratch, AArch64Kind.QWORD);
 338 
 339             // Compare index against jump table bounds
 340             int highKey = lowKey + targets.length - 1;
 341             masm.sub(32, idxScratchReg, indexReg, lowKey);
 342             masm.cmp(32, idxScratchReg, highKey - lowKey);
 343 
 344             // Jump to default target if index is not within the jump table
 345             if (defaultTarget != null) {
 346                 masm.branchConditionally(ConditionFlag.HI, defaultTarget.label());
 347             }
 348 
 349             Label jumpTable = new Label();
 350             masm.adr(scratchReg, jumpTable);
 351             masm.add(64, scratchReg, scratchReg, idxScratchReg, ExtendType.UXTW, 2);
 352             masm.jmp(scratchReg);
 353             masm.bind(jumpTable);
 354             // emit jump table entries
 355             for (LabelRef target : targets) {
 356                 masm.jmp(target.label());
 357             }
 358             JumpTable jt = new JumpTable(jumpTable.position(), lowKey, highKey - 1, 4);
 359             crb.compilationResult.addAnnotation(jt);
 360         }
 361     }
 362 
 363     private static void emitCompare(CompilationResultBuilder crb, AArch64MacroAssembler masm, Value key, Value scratchValue, ConstantValue c) {
 364         long imm = c.getJavaConstant().asLong();
 365         final int size = key.getPlatformKind().getSizeInBytes() * Byte.SIZE;
 366         if (AArch64MacroAssembler.isComparisonImmediate(imm)) {
 367             masm.cmp(size, asRegister(key), (int) imm);
 368         } else {
 369             AArch64Move.move(crb, masm, asAllocatableValue(scratchValue), c);
 370             masm.cmp(size, asRegister(key), asRegister(scratchValue));
 371         }
 372     }
 373 
 374 }