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 }