1 /*
   2  * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.lir.amd64;
  24 
  25 import static jdk.vm.ci.code.ValueUtil.asRegister;
  26 import static jdk.vm.ci.code.ValueUtil.isRegister;
  27 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.CONST;
  28 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.HINT;
  29 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.ILLEGAL;
  30 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.REG;
  31 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.STACK;


  32 
  33 import org.graalvm.compiler.asm.Label;

  34 import org.graalvm.compiler.asm.amd64.AMD64Address;
  35 import org.graalvm.compiler.asm.amd64.AMD64Address.Scale;
  36 import org.graalvm.compiler.asm.amd64.AMD64Assembler.ConditionFlag;
  37 import org.graalvm.compiler.asm.amd64.AMD64MacroAssembler;
  38 import org.graalvm.compiler.code.CompilationResult.JumpTable;
  39 import org.graalvm.compiler.core.common.NumUtil;
  40 import org.graalvm.compiler.core.common.calc.Condition;
  41 import org.graalvm.compiler.debug.GraalError;
  42 import org.graalvm.compiler.lir.LIRInstructionClass;
  43 import org.graalvm.compiler.lir.LabelRef;
  44 import org.graalvm.compiler.lir.Opcode;
  45 import org.graalvm.compiler.lir.StandardOp;
  46 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
  47 import org.graalvm.compiler.lir.SwitchStrategy;
  48 import org.graalvm.compiler.lir.SwitchStrategy.BaseSwitchClosure;
  49 import org.graalvm.compiler.lir.Variable;
  50 import org.graalvm.compiler.lir.asm.CompilationResultBuilder;
  51 
  52 import jdk.vm.ci.amd64.AMD64;
  53 import jdk.vm.ci.amd64.AMD64.CPUFeature;
  54 import jdk.vm.ci.amd64.AMD64Kind;
  55 import jdk.vm.ci.code.Register;
  56 import jdk.vm.ci.meta.AllocatableValue;
  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 AMD64ControlFlow {
  62 
  63     public static final class ReturnOp extends AMD64BlockEndOp implements BlockEndOp {
  64         public static final LIRInstructionClass<ReturnOp> TYPE = LIRInstructionClass.create(ReturnOp.class);
  65         @Use({REG, ILLEGAL}) protected Value x;
  66 
  67         public ReturnOp(Value x) {
  68             super(TYPE);
  69             this.x = x;
  70         }
  71 
  72         @Override
  73         public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) {
  74             crb.frameContext.leave(crb);
  75             /*
  76              * We potentially return to the interpreter, and that's an AVX-SSE transition. The only
  77              * live value at this point should be the return value in either rax, or in xmm0 with
  78              * the upper half of the register unused, so we don't destroy any value here.
  79              */
  80             if (masm.supports(CPUFeature.AVX)) {
  81                 masm.vzeroupper();
  82             }
  83             masm.ret(0);
  84         }
  85     }
  86 
  87     public static class BranchOp extends AMD64BlockEndOp implements StandardOp.BranchOp {
  88         public static final LIRInstructionClass<BranchOp> TYPE = LIRInstructionClass.create(BranchOp.class);
  89         protected final ConditionFlag condition;
  90         protected final LabelRef trueDestination;
  91         protected final LabelRef falseDestination;
  92 
  93         private final double trueDestinationProbability;
  94 
  95         public BranchOp(Condition condition, LabelRef trueDestination, LabelRef falseDestination, double trueDestinationProbability) {
  96             this(intCond(condition), trueDestination, falseDestination, trueDestinationProbability);
  97         }
  98 
  99         public BranchOp(ConditionFlag condition, LabelRef trueDestination, LabelRef falseDestination, double trueDestinationProbability) {
 100             this(TYPE, condition, trueDestination, falseDestination, trueDestinationProbability);
 101         }
 102 
 103         protected BranchOp(LIRInstructionClass<? extends BranchOp> c, ConditionFlag condition, LabelRef trueDestination, LabelRef falseDestination, double trueDestinationProbability) {
 104             super(c);
 105             this.condition = condition;
 106             this.trueDestination = trueDestination;
 107             this.falseDestination = falseDestination;
 108             this.trueDestinationProbability = trueDestinationProbability;
 109         }
 110 
 111         @Override
 112         public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) {
 113             boolean isNegated = false;
 114             int jccPos = masm.position();
 115             /*
 116              * The strategy for emitting jumps is: If either trueDestination or falseDestination is
 117              * the successor block, assume the block scheduler did the correct thing and jcc to the
 118              * other. Otherwise, we need a jcc followed by a jmp. Use the branch probability to make
 119              * sure it is more likely to branch on the jcc (= less likely to execute both the jcc
 120              * and the jmp instead of just the jcc). In the case of loops, that means the jcc is the
 121              * back-edge.
 122              */
 123             if (crb.isSuccessorEdge(trueDestination)) {
 124                 jcc(masm, true, falseDestination);
 125                 isNegated = true;
 126             } else if (crb.isSuccessorEdge(falseDestination)) {
 127                 jcc(masm, false, trueDestination);
 128             } else if (trueDestinationProbability < 0.5) {
 129                 jcc(masm, true, falseDestination);
 130                 masm.jmp(trueDestination.label());
 131                 isNegated = true;
 132             } else {
 133                 jcc(masm, false, trueDestination);
 134                 masm.jmp(falseDestination.label());
 135             }
 136             crb.recordBranch(jccPos, isNegated);
 137         }
 138 
 139         protected void jcc(AMD64MacroAssembler masm, boolean negate, LabelRef target) {
 140             masm.jcc(negate ? condition.negate() : condition, target.label());
 141         }
 142     }
 143 
 144     public static final class FloatBranchOp extends BranchOp {
 145         public static final LIRInstructionClass<FloatBranchOp> TYPE = LIRInstructionClass.create(FloatBranchOp.class);
 146         protected boolean unorderedIsTrue;
 147 
 148         public FloatBranchOp(Condition condition, boolean unorderedIsTrue, LabelRef trueDestination, LabelRef falseDestination, double trueDestinationProbability) {
 149             super(TYPE, floatCond(condition), trueDestination, falseDestination, trueDestinationProbability);
 150             this.unorderedIsTrue = unorderedIsTrue;
 151         }
 152 
 153         @Override
 154         protected void jcc(AMD64MacroAssembler masm, boolean negate, LabelRef target) {
 155             floatJcc(masm, negate ? condition.negate() : condition, negate ? !unorderedIsTrue : unorderedIsTrue, target.label());
 156         }
 157     }
 158 
 159     public static class StrategySwitchOp extends AMD64BlockEndOp {
 160         public static final LIRInstructionClass<StrategySwitchOp> TYPE = LIRInstructionClass.create(StrategySwitchOp.class);
 161         protected final Constant[] keyConstants;
 162         private final LabelRef[] keyTargets;
 163         private LabelRef defaultTarget;
 164         @Alive({REG}) protected Value key;
 165         @Temp({REG, ILLEGAL}) protected Value scratch;
 166         protected final SwitchStrategy strategy;
 167 
 168         public StrategySwitchOp(SwitchStrategy strategy, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch) {
 169             this(TYPE, strategy, keyTargets, defaultTarget, key, scratch);
 170         }
 171 
 172         protected StrategySwitchOp(LIRInstructionClass<? extends StrategySwitchOp> c, SwitchStrategy strategy, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch) {
 173             super(c);
 174             this.strategy = strategy;
 175             this.keyConstants = strategy.getKeyConstants();
 176             this.keyTargets = keyTargets;
 177             this.defaultTarget = defaultTarget;
 178             this.key = key;
 179             this.scratch = scratch;
 180             assert keyConstants.length == keyTargets.length;
 181             assert keyConstants.length == strategy.keyProbabilities.length;
 182         }
 183 
 184         @Override
 185         public void emitCode(final CompilationResultBuilder crb, final AMD64MacroAssembler masm) {
 186             strategy.run(new SwitchClosure(asRegister(key), crb, masm));
 187         }
 188 
 189         public class SwitchClosure extends BaseSwitchClosure {
 190 
 191             protected final Register keyRegister;
 192             protected final CompilationResultBuilder crb;
 193             protected final AMD64MacroAssembler masm;
 194 
 195             protected SwitchClosure(Register keyRegister, CompilationResultBuilder crb, AMD64MacroAssembler masm) {
 196                 super(crb, masm, keyTargets, defaultTarget);
 197                 this.keyRegister = keyRegister;
 198                 this.crb = crb;
 199                 this.masm = masm;
 200             }
 201 
 202             protected void emitComparison(Constant c) {
 203                 JavaConstant jc = (JavaConstant) c;
 204                 switch (jc.getJavaKind()) {
 205                     case Int:
 206                         long lc = jc.asLong();
 207                         assert NumUtil.isInt(lc);
 208                         masm.cmpl(keyRegister, (int) lc);
 209                         break;
 210                     case Long:
 211                         masm.cmpq(keyRegister, (AMD64Address) crb.asLongConstRef(jc));
 212                         break;
 213                     case Object:
 214                         AMD64Move.const2reg(crb, masm, asRegister(scratch), jc);
 215                         masm.cmpptr(keyRegister, asRegister(scratch));
 216                         break;
 217                     default:
 218                         throw new GraalError("switch only supported for int, long and object");
 219                 }
 220             }
 221 
 222             @Override
 223             protected void conditionalJump(int index, Condition condition, Label target) {
 224                 emitComparison(keyConstants[index]);
 225                 masm.jcc(intCond(condition), target);
 226             }
 227         }
 228     }
 229 
 230     public static final class TableSwitchOp extends AMD64BlockEndOp {
 231         public static final LIRInstructionClass<TableSwitchOp> TYPE = LIRInstructionClass.create(TableSwitchOp.class);
 232         private final int lowKey;
 233         private final LabelRef defaultTarget;
 234         private final LabelRef[] targets;
 235         @Use protected Value index;
 236         @Temp({REG, HINT}) protected Value idxScratch;
 237         @Temp protected Value scratch;
 238 
 239         public TableSwitchOp(final int lowKey, final LabelRef defaultTarget, final LabelRef[] targets, Value index, Variable scratch, Variable idxScratch) {
 240             super(TYPE);
 241             this.lowKey = lowKey;
 242             this.defaultTarget = defaultTarget;
 243             this.targets = targets;
 244             this.index = index;
 245             this.scratch = scratch;
 246             this.idxScratch = idxScratch;
 247         }
 248 
 249         @Override
 250         public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) {
 251             Register indexReg = asRegister(index, AMD64Kind.DWORD);
 252             Register idxScratchReg = asRegister(idxScratch, AMD64Kind.DWORD);
 253             Register scratchReg = asRegister(scratch, AMD64Kind.QWORD);
 254 
 255             if (!indexReg.equals(idxScratchReg)) {
 256                 masm.movl(idxScratchReg, indexReg);
 257             }
 258 
 259             // Compare index against jump table bounds
 260             int highKey = lowKey + targets.length - 1;
 261             if (lowKey != 0) {
 262                 // subtract the low value from the switch value
 263                 masm.subl(idxScratchReg, lowKey);
 264                 masm.cmpl(idxScratchReg, highKey - lowKey);
 265             } else {
 266                 masm.cmpl(idxScratchReg, highKey);
 267             }
 268 
 269             // Jump to default target if index is not within the jump table
 270             if (defaultTarget != null) {
 271                 masm.jcc(ConditionFlag.Above, defaultTarget.label());
 272             }
 273 
 274             // Set scratch to address of jump table
 275             masm.leaq(scratchReg, new AMD64Address(AMD64.rip, 0));
 276             final int afterLea = masm.position();
 277 
 278             // Load jump table entry into scratch and jump to it
 279             masm.movslq(idxScratchReg, new AMD64Address(scratchReg, idxScratchReg, Scale.Times4, 0));
 280             masm.addq(scratchReg, idxScratchReg);
 281             masm.jmp(scratchReg);
 282 
 283             // Inserting padding so that jump table address is 4-byte aligned
 284             if ((masm.position() & 0x3) != 0) {
 285                 masm.nop(4 - (masm.position() & 0x3));
 286             }
 287 
 288             // Patch LEA instruction above now that we know the position of the jump table
 289             // TODO this is ugly and should be done differently
 290             final int jumpTablePos = masm.position();
 291             final int leaDisplacementPosition = afterLea - 4;
 292             masm.emitInt(jumpTablePos - afterLea, leaDisplacementPosition);
 293 
 294             // Emit jump table entries
 295             for (LabelRef target : targets) {
 296                 Label label = target.label();
 297                 int offsetToJumpTableBase = masm.position() - jumpTablePos;
 298                 if (label.isBound()) {
 299                     int imm32 = label.position() - jumpTablePos;
 300                     masm.emitInt(imm32);
 301                 } else {
 302                     label.addPatchAt(masm.position());
 303 
 304                     masm.emitByte(0); // pseudo-opcode for jump table entry
 305                     masm.emitShort(offsetToJumpTableBase);
 306                     masm.emitByte(0); // padding to make jump table entry 4 bytes wide
 307                 }
 308             }
 309 
 310             JumpTable jt = new JumpTable(jumpTablePos, lowKey, highKey, 4);
 311             crb.compilationResult.addAnnotation(jt);
 312         }
 313     }
 314 
 315     @Opcode("SETcc")
 316     public static final class CondSetOp extends AMD64LIRInstruction {
 317         public static final LIRInstructionClass<CondSetOp> TYPE = LIRInstructionClass.create(CondSetOp.class);
 318         @Def({REG, HINT}) protected Value result;
 319         private final ConditionFlag condition;
 320 
 321         public CondSetOp(Variable result, Condition condition) {
 322             super(TYPE);
 323             this.result = result;
 324             this.condition = intCond(condition);
 325         }
 326 
 327         @Override
 328         public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) {
 329             setcc(masm, result, condition);
 330         }
 331     }
 332 
 333     @Opcode("SETcc")
 334     public static final class FloatCondSetOp extends AMD64LIRInstruction {
 335         public static final LIRInstructionClass<FloatCondSetOp> TYPE = LIRInstructionClass.create(FloatCondSetOp.class);
 336         @Def({REG, HINT}) protected Value result;
 337         private final ConditionFlag condition;
 338 
 339         public FloatCondSetOp(Variable result, Condition condition) {
 340             super(TYPE);
 341             this.result = result;
 342             this.condition = floatCond(condition);
 343         }
 344 
 345         @Override
 346         public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) {
 347             setcc(masm, result, condition);
 348         }
 349     }
 350 
 351     @Opcode("CMOVE")
 352     public static final class CondMoveOp extends AMD64LIRInstruction {
 353         public static final LIRInstructionClass<CondMoveOp> TYPE = LIRInstructionClass.create(CondMoveOp.class);
 354         @Def({REG, HINT}) protected Value result;
 355         @Alive({REG}) protected Value trueValue;
 356         @Use({REG, STACK, CONST}) protected Value falseValue;
 357         private final ConditionFlag condition;
 358 
 359         public CondMoveOp(Variable result, Condition condition, AllocatableValue trueValue, Value falseValue) {
 360             super(TYPE);
 361             this.result = result;
 362             this.condition = intCond(condition);
 363             this.trueValue = trueValue;
 364             this.falseValue = falseValue;
 365         }
 366 
 367         @Override
 368         public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) {
 369             cmove(crb, masm, result, false, condition, false, trueValue, falseValue);
 370         }
 371     }
 372 
 373     @Opcode("CMOVE")
 374     public static final class FloatCondMoveOp extends AMD64LIRInstruction {
 375         public static final LIRInstructionClass<FloatCondMoveOp> TYPE = LIRInstructionClass.create(FloatCondMoveOp.class);
 376         @Def({REG}) protected Value result;
 377         @Alive({REG}) protected Value trueValue;
 378         @Alive({REG}) protected Value falseValue;
 379         private final ConditionFlag condition;
 380         private final boolean unorderedIsTrue;
 381 
 382         public FloatCondMoveOp(Variable result, Condition condition, boolean unorderedIsTrue, Variable trueValue, Variable falseValue) {
 383             super(TYPE);
 384             this.result = result;
 385             this.condition = floatCond(condition);
 386             this.unorderedIsTrue = unorderedIsTrue;
 387             this.trueValue = trueValue;
 388             this.falseValue = falseValue;
 389         }
 390 
 391         @Override
 392         public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) {
 393             cmove(crb, masm, result, true, condition, unorderedIsTrue, trueValue, falseValue);
 394         }
 395     }
 396 
 397     private static void floatJcc(AMD64MacroAssembler masm, ConditionFlag condition, boolean unorderedIsTrue, Label label) {
 398         Label endLabel = new Label();
 399         if (unorderedIsTrue && !trueOnUnordered(condition)) {
 400             masm.jcc(ConditionFlag.Parity, label);
 401         } else if (!unorderedIsTrue && trueOnUnordered(condition)) {
 402             masm.jccb(ConditionFlag.Parity, endLabel);
 403         }
 404         masm.jcc(condition, label);
 405         masm.bind(endLabel);
 406     }
 407 
 408     private static void cmove(CompilationResultBuilder crb, AMD64MacroAssembler masm, Value result, boolean isFloat, ConditionFlag condition, boolean unorderedIsTrue, Value trueValue,
 409                     Value falseValue) {
 410         // check that we don't overwrite an input operand before it is used.
 411         assert !result.equals(trueValue);
 412 
 413         AMD64Move.move(crb, masm, result, falseValue);
 414         cmove(crb, masm, result, condition, trueValue);
 415 
 416         if (isFloat) {
 417             if (unorderedIsTrue && !trueOnUnordered(condition)) {
 418                 cmove(crb, masm, result, ConditionFlag.Parity, trueValue);
 419             } else if (!unorderedIsTrue && trueOnUnordered(condition)) {
 420                 cmove(crb, masm, result, ConditionFlag.Parity, falseValue);
 421             }
 422         }
 423     }
 424 
 425     private static void cmove(CompilationResultBuilder crb, AMD64MacroAssembler masm, Value result, ConditionFlag cond, Value other) {
 426         if (isRegister(other)) {
 427             assert !asRegister(other).equals(asRegister(result)) : "other already overwritten by previous move";
 428             switch ((AMD64Kind) other.getPlatformKind()) {
 429                 case BYTE:
 430                 case WORD:
 431                 case DWORD:
 432                     masm.cmovl(cond, asRegister(result), asRegister(other));
 433                     break;
 434                 case QWORD:
 435                     masm.cmovq(cond, asRegister(result), asRegister(other));
 436                     break;
 437                 default:
 438                     throw GraalError.shouldNotReachHere();
 439             }
 440         } else {
 441             AMD64Address addr = (AMD64Address) crb.asAddress(other);
 442             switch ((AMD64Kind) other.getPlatformKind()) {
 443                 case BYTE:
 444                 case WORD:
 445                 case DWORD:
 446                     masm.cmovl(cond, asRegister(result), addr);
 447                     break;
 448                 case QWORD:
 449                     masm.cmovq(cond, asRegister(result), addr);
 450                     break;
 451                 default:
 452                     throw GraalError.shouldNotReachHere();
 453             }
 454         }
 455     }
 456 
 457     private static void setcc(AMD64MacroAssembler masm, Value result, ConditionFlag cond) {
 458         switch ((AMD64Kind) result.getPlatformKind()) {
 459             case BYTE:
 460             case WORD:
 461             case DWORD:
 462                 masm.setl(cond, asRegister(result));
 463                 break;
 464             case QWORD:
 465                 masm.setq(cond, asRegister(result));
 466                 break;
 467             default:
 468                 throw GraalError.shouldNotReachHere();
 469         }
 470     }
 471 
 472     private static ConditionFlag intCond(Condition cond) {
 473         switch (cond) {
 474             case EQ:
 475                 return ConditionFlag.Equal;
 476             case NE:
 477                 return ConditionFlag.NotEqual;
 478             case LT:
 479                 return ConditionFlag.Less;
 480             case LE:
 481                 return ConditionFlag.LessEqual;
 482             case GE:
 483                 return ConditionFlag.GreaterEqual;
 484             case GT:
 485                 return ConditionFlag.Greater;
 486             case BE:
 487                 return ConditionFlag.BelowEqual;
 488             case AE:
 489                 return ConditionFlag.AboveEqual;
 490             case AT:
 491                 return ConditionFlag.Above;
 492             case BT:
 493                 return ConditionFlag.Below;
 494             default:
 495                 throw GraalError.shouldNotReachHere();
 496         }
 497     }
 498 
 499     private static ConditionFlag floatCond(Condition cond) {
 500         switch (cond) {
 501             case EQ:
 502                 return ConditionFlag.Equal;
 503             case NE:
 504                 return ConditionFlag.NotEqual;
 505             case LT:
 506                 return ConditionFlag.Below;
 507             case LE:
 508                 return ConditionFlag.BelowEqual;
 509             case GE:
 510                 return ConditionFlag.AboveEqual;
 511             case GT:
 512                 return ConditionFlag.Above;
 513             default:
 514                 throw GraalError.shouldNotReachHere();
 515         }
 516     }
 517 
 518     public static boolean trueOnUnordered(Condition condition) {
 519         return trueOnUnordered(floatCond(condition));
 520     }
 521 
 522     private static boolean trueOnUnordered(ConditionFlag condition) {
 523         switch (condition) {
 524             case AboveEqual:
 525             case NotEqual:
 526             case Above:
 527             case Less:
 528             case Overflow:
 529                 return false;
 530             case Equal:
 531             case BelowEqual:
 532             case Below:
 533             case GreaterEqual:
 534             case NoOverflow:
 535                 return true;
 536             default:
 537                 throw GraalError.shouldNotReachHere();
 538         }
 539     }
 540 }
--- EOF ---