Mercurial > hg > truffle
changeset 15691:6a13c422fca4
API for high word multiplication.
line wrap: on
line diff
--- a/graal/com.oracle.graal.asm.amd64/src/com/oracle/graal/asm/amd64/AMD64Assembler.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.asm.amd64/src/com/oracle/graal/asm/amd64/AMD64Assembler.java Thu May 15 19:03:16 2014 +0200 @@ -784,15 +784,39 @@ } public final void idivl(Register src) { - int encode = prefixAndEncode(src.encoding); + int encode = prefixAndEncode(7, src.encoding); emitByte(0xF7); - emitByte(0xF8 | encode); + emitByte(0xC0 | encode); } public final void divl(Register src) { - int encode = prefixAndEncode(src.encoding); + int encode = prefixAndEncode(6, src.encoding); + emitByte(0xF7); + emitByte(0xC0 | encode); + } + + public final void mull(Register src) { + int encode = prefixAndEncode(4, src.encoding); + emitByte(0xF7); + emitByte(0xC0 | encode); + } + + public final void mull(AMD64Address src) { + prefix(src); emitByte(0xF7); - emitByte(0xF0 | encode); + emitOperandHelper(4, src); + } + + public final void imull(Register src) { + int encode = prefixAndEncode(5, src.encoding); + emitByte(0xF7); + emitByte(0xC0 | encode); + } + + public final void imull(AMD64Address src) { + prefix(src); + emitByte(0xF7); + emitOperandHelper(5, src); } public final void imull(Register dst, Register src) { @@ -2346,15 +2370,39 @@ } public final void divq(Register src) { - int encode = prefixqAndEncode(src.encoding); + int encode = prefixqAndEncode(6, src.encoding); emitByte(0xF7); - emitByte(0xF0 | encode); + emitByte(0xC0 | encode); } public final void idivq(Register src) { - int encode = prefixqAndEncode(src.encoding); + int encode = prefixqAndEncode(7, src.encoding); + emitByte(0xF7); + emitByte(0xC0 | encode); + } + + public final void mulq(Register src) { + int encode = prefixqAndEncode(4, src.encoding); + emitByte(0xF7); + emitByte(0xC0 | encode); + } + + public final void mulq(AMD64Address src) { + prefixq(src); emitByte(0xF7); - emitByte(0xF8 | encode); + emitOperandHelper(4, src); + } + + public final void imulq(Register src) { + int encode = prefixqAndEncode(5, src.encoding); + emitByte(0xF7); + emitByte(0xC0 | encode); + } + + public final void imulq(AMD64Address src) { + prefixq(src); + emitByte(0xF7); + emitOperandHelper(5, src); } public final void imulq(Register dst, Register src) {
--- a/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java Thu May 15 19:03:16 2014 +0200 @@ -601,6 +601,37 @@ } } + private Value emitMulHigh(AMD64Arithmetic opcode, Value a, Value b) { + MulHighOp mulHigh = new MulHighOp(opcode, asAllocatable(b)); + emitMove(mulHigh.x, a); + append(mulHigh); + return emitMove(mulHigh.highResult); + } + + @Override + public Value emitMulHigh(Value a, Value b) { + switch (a.getKind().getStackKind()) { + case Int: + return emitMulHigh(IMUL, a, b); + case Long: + return emitMulHigh(LMUL, a, b); + default: + throw GraalInternalError.shouldNotReachHere(); + } + } + + @Override + public Value emitUMulHigh(Value a, Value b) { + switch (a.getKind().getStackKind()) { + case Int: + return emitMulHigh(IUMUL, a, b); + case Long: + return emitMulHigh(LUMUL, a, b); + default: + throw GraalInternalError.shouldNotReachHere(); + } + } + public Value emitBinaryMemory(AMD64Arithmetic op, Kind kind, AllocatableValue a, AMD64AddressValue location, LIRFrameState state) { Variable result = newVariable(a.getKind()); append(new BinaryMemory(op, kind, result, a, location, state));
--- a/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java Thu May 15 19:03:16 2014 +0200 @@ -404,6 +404,16 @@ } @Override + public Value emitMulHigh(Value a, Value b) { + throw GraalInternalError.unimplemented(); + } + + @Override + public Value emitUMulHigh(Value a, Value b) { + throw GraalInternalError.unimplemented(); + } + + @Override public Value emitDiv(Value a, Value b, LIRFrameState state) { Variable result = newVariable(a.getKind()); switch (a.getKind()) {
--- a/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java Thu May 15 19:03:16 2014 +0200 @@ -485,6 +485,16 @@ } @Override + public Value emitMulHigh(Value a, Value b) { + throw GraalInternalError.unimplemented(); + } + + @Override + public Value emitUMulHigh(Value a, Value b) { + throw GraalInternalError.unimplemented(); + } + + @Override public Value emitDiv(Value a, Value b, LIRFrameState state) { Variable result = newVariable(a.getKind()); switch (a.getKind()) {
--- a/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java Thu May 15 19:03:16 2014 +0200 @@ -580,6 +580,16 @@ } @Override + public Value emitMulHigh(Value a, Value b) { + throw GraalInternalError.unimplemented(); + } + + @Override + public Value emitUMulHigh(Value a, Value b) { + throw GraalInternalError.unimplemented(); + } + + @Override public Value emitDiv(Value a, Value b, LIRFrameState state) { Variable result = newVariable(a.getKind()); switch (a.getKind().getStackKind()) {
--- a/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64Arithmetic.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64Arithmetic.java Thu May 15 19:03:16 2014 +0200 @@ -39,8 +39,8 @@ // @formatter:off - IADD, ISUB, IMUL, IDIV, IDIVREM, IREM, IUDIV, IUREM, IAND, IOR, IXOR, ISHL, ISHR, IUSHR, IROL, IROR, - LADD, LSUB, LMUL, LDIV, LDIVREM, LREM, LUDIV, LUREM, LAND, LOR, LXOR, LSHL, LSHR, LUSHR, LROL, LROR, + IADD, ISUB, IMUL, IUMUL, IDIV, IDIVREM, IREM, IUDIV, IUREM, IAND, IOR, IXOR, ISHL, ISHR, IUSHR, IROL, IROR, + LADD, LSUB, LMUL, LUMUL, LDIV, LDIVREM, LREM, LUDIV, LUREM, LAND, LOR, LXOR, LSHL, LSHR, LUSHR, LROL, LROR, FADD, FSUB, FMUL, FDIV, FREM, FAND, FOR, FXOR, DADD, DSUB, DMUL, DDIV, DREM, DAND, DOR, DXOR, INEG, LNEG, INOT, LNOT, @@ -342,6 +342,64 @@ } } + public static class MulHighOp extends AMD64LIRInstruction { + + @Opcode private final AMD64Arithmetic opcode; + @Def({REG}) public AllocatableValue lowResult; + @Def({REG}) public AllocatableValue highResult; + @Use({REG}) public AllocatableValue x; + @Use({REG, STACK}) public AllocatableValue y; + + public MulHighOp(AMD64Arithmetic opcode, AllocatableValue y) { + PlatformKind kind = y.getPlatformKind(); + + this.opcode = opcode; + this.x = AMD64.rax.asValue(kind); + this.y = y; + this.lowResult = AMD64.rax.asValue(kind); + this.highResult = AMD64.rdx.asValue(kind); + } + + @Override + public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) { + if (isRegister(y)) { + switch (opcode) { + case IMUL: + masm.imull(asRegister(y)); + break; + case IUMUL: + masm.mull(asRegister(y)); + break; + case LMUL: + masm.imulq(asRegister(y)); + break; + case LUMUL: + masm.mulq(asRegister(y)); + break; + default: + throw GraalInternalError.shouldNotReachHere(); + } + } else { + switch (opcode) { + case IMUL: + masm.imull((AMD64Address) crb.asAddress(y)); + break; + case IUMUL: + masm.mull((AMD64Address) crb.asAddress(y)); + break; + case LMUL: + masm.imulq((AMD64Address) crb.asAddress(y)); + break; + case LUMUL: + masm.mulq((AMD64Address) crb.asAddress(y)); + break; + default: + throw GraalInternalError.shouldNotReachHere(); + } + } + } + } + public static class DivRemOp extends AMD64LIRInstruction { @Opcode private final AMD64Arithmetic opcode;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/ArithmeticLIRGenerator.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/ArithmeticLIRGenerator.java Thu May 15 19:03:16 2014 +0200 @@ -42,6 +42,10 @@ Value emitMul(Value a, Value b); + Value emitMulHigh(Value a, Value b); + + Value emitUMulHigh(Value a, Value b); + Value emitDiv(Value a, Value b, LIRFrameState state); Value emitRem(Value a, Value b, LIRFrameState state);
--- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/ExactMathTest.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/ExactMathTest.java Thu May 15 19:03:16 2014 +0200 @@ -62,6 +62,20 @@ } @Test + public void testMulHigh() { + test("mulHigh", 7, 15); + test("mulHigh", Integer.MAX_VALUE, 15); + test("mulHigh", Integer.MIN_VALUE, 15); + } + + @Test + public void testMulHighUnsigned() { + test("mulHighUnsigned", 7, 15); + test("mulHighUnsigned", Integer.MAX_VALUE, 15); + test("mulHighUnsigned", Integer.MIN_VALUE, 15); + } + + @Test public void testLongAdd() { test("longAdd", (long) Integer.MAX_VALUE, 2L); test("longAdd", Long.MAX_VALUE, 2L); @@ -80,6 +94,20 @@ test("longSub", Long.MIN_VALUE, 2L); } + @Test + public void testLongMulHigh() { + test("longMulHigh", 7L, 15L); + test("longMulHigh", Long.MAX_VALUE, 15L); + test("longMulHigh", Long.MIN_VALUE, 15L); + } + + @Test + public void testLongMulHighUnsigned() { + test("longMulHighUnsigned", 7L, 15L); + test("longMulHighUnsigned", Long.MAX_VALUE, 15L); + test("longMulHighUnsigned", Long.MIN_VALUE, 15L); + } + public static int add(int a, int b) { return ExactMath.addExact(a, b); } @@ -92,6 +120,14 @@ return ExactMath.subtractExact(a, b); } + public static int mulHigh(int a, int b) { + return ExactMath.multiplyHigh(a, b); + } + + public static int mulHighUnsigned(int a, int b) { + return ExactMath.multiplyHighUnsigned(a, b); + } + public static long longAdd(long a, long b) { return ExactMath.addExact(a, b); } @@ -103,4 +139,12 @@ public static long longSub(long a, long b) { return ExactMath.subtractExact(a, b); } + + public static long longMulHigh(long a, long b) { + return ExactMath.multiplyHigh(a, b); + } + + public static long longMulHighUnsigned(long a, long b) { + return ExactMath.multiplyHighUnsigned(a, b); + } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerMulHighNode.java Thu May 15 19:03:16 2014 +0200 @@ -0,0 +1,75 @@ +/* + * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.truffle.nodes.arithmetic; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.type.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.truffle.api.*; + +@NodeInfo(shortName = "*H") +public class IntegerMulHighNode extends IntegerArithmeticNode { + + public IntegerMulHighNode(ValueNode x, ValueNode y) { + this(x.stamp().unrestricted(), x, y); + } + + public IntegerMulHighNode(Stamp stamp, ValueNode x, ValueNode y) { + super(stamp, x, y); + } + + @Override + public Constant evalConst(Constant... inputs) { + assert inputs.length == 2 && inputs[0].getKind() == inputs[1].getKind(); + switch (inputs[0].getKind()) { + case Int: + return Constant.forInt(ExactMath.multiplyHigh(inputs[0].asInt(), inputs[1].asInt())); + case Long: + return Constant.forLong(ExactMath.multiplyHigh(inputs[0].asLong(), inputs[1].asLong())); + default: + throw GraalInternalError.unimplemented(); + } + } + + @Override + public void generate(NodeMappableLIRBuilder builder, ArithmeticLIRGenerator gen) { + Value a = builder.operand(x()); + Value b = builder.operand(y()); + builder.setResult(this, gen.emitMulHigh(a, b)); + } + + @NodeIntrinsic + public static int multiplyHigh(int a, int b) { + return ExactMath.multiplyHigh(a, b); + } + + @NodeIntrinsic + public static long multiplyHigh(long a, long b) { + return ExactMath.multiplyHigh(a, b); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/UnsignedMulHighNode.java Thu May 15 19:03:16 2014 +0200 @@ -0,0 +1,75 @@ +/* + * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.truffle.nodes.arithmetic; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.type.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.truffle.api.*; + +@NodeInfo(shortName = "|*H|") +public class UnsignedMulHighNode extends IntegerArithmeticNode { + + public UnsignedMulHighNode(ValueNode x, ValueNode y) { + this(x.stamp().unrestricted(), x, y); + } + + public UnsignedMulHighNode(Stamp stamp, ValueNode x, ValueNode y) { + super(stamp, x, y); + } + + @Override + public Constant evalConst(Constant... inputs) { + assert inputs.length == 2 && inputs[0].getKind() == inputs[1].getKind(); + switch (inputs[0].getKind()) { + case Int: + return Constant.forInt(ExactMath.multiplyHighUnsigned(inputs[0].asInt(), inputs[1].asInt())); + case Long: + return Constant.forLong(ExactMath.multiplyHighUnsigned(inputs[0].asLong(), inputs[1].asLong())); + default: + throw GraalInternalError.unimplemented(); + } + } + + @Override + public void generate(NodeMappableLIRBuilder builder, ArithmeticLIRGenerator gen) { + Value a = builder.operand(x()); + Value b = builder.operand(y()); + builder.setResult(this, gen.emitUMulHigh(a, b)); + } + + @NodeIntrinsic + public static int multiplyHighUnsigned(int a, int b) { + return ExactMath.multiplyHighUnsigned(a, b); + } + + @NodeIntrinsic + public static long multiplyHighUnsigned(long a, long b) { + return ExactMath.multiplyHighUnsigned(a, b); + } +}
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/substitutions/ExactMathSubstitutions.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/substitutions/ExactMathSubstitutions.java Thu May 15 19:03:16 2014 +0200 @@ -62,4 +62,24 @@ public static long multiplyExact(long x, long y) { return IntegerMulExactNode.multiplyExact(x, y); } + + @MethodSubstitution + public static int multiplyHigh(int x, int y) { + return IntegerMulHighNode.multiplyHigh(x, y); + } + + @MethodSubstitution + public static int multiplyHighUnsigned(int x, int y) { + return UnsignedMulHighNode.multiplyHighUnsigned(x, y); + } + + @MethodSubstitution + public static long multiplyHigh(long x, long y) { + return IntegerMulHighNode.multiplyHigh(x, y); + } + + @MethodSubstitution + public static long multiplyHighUnsigned(long x, long y) { + return UnsignedMulHighNode.multiplyHighUnsigned(x, y); + } }
--- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/ExactMath.java Thu May 15 18:13:24 2014 +0200 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/ExactMath.java Thu May 15 19:03:16 2014 +0200 @@ -91,4 +91,54 @@ } return r; } + + public static int multiplyHigh(int x, int y) { + long r = (long) x * (long) y; + return (int) (r >> 32); + } + + public static int multiplyHighUnsigned(int x, int y) { + long xl = x & 0xFFFFFFFFL; + long yl = y & 0xFFFFFFFFL; + long r = xl * yl; + return (int) (r >> 32); + } + + public static long multiplyHigh(long x, long y) { + long x0, y0, z0; + long x1, y1, z1, z2, t; + + x0 = x & 0xFFFFFFFFL; + x1 = x >> 32; + + y0 = y & 0xFFFFFFFFL; + y1 = y >> 32; + + z0 = x0 * y0; + t = x1 * y0 + (z0 >>> 32); + z1 = t & 0xFFFFFFFFL; + z2 = t >> 32; + z1 += x0 * y1; + + return x1 * y1 + z2 + (z1 >> 32); + } + + public static long multiplyHighUnsigned(long x, long y) { + long x0, y0, z0; + long x1, y1, z1, z2, t; + + x0 = x & 0xFFFFFFFFL; + x1 = x >>> 32; + + y0 = y & 0xFFFFFFFFL; + y1 = y >>> 32; + + z0 = x0 * y0; + t = x1 * y0 + (z0 >>> 32); + z1 = t & 0xFFFFFFFFL; + z2 = t >>> 32; + z1 += x0 * y1; + + return x1 * y1 + z2 + (z1 >>> 32); + } }