# HG changeset patch # User Doug Simon # Date 1384984239 -3600 # Node ID f705fc04faa56af867f52f885ac887f58bb1d264 # Parent c0085eefbd42eb5049395e85144be6753b3945c9 HSAIL: adds support for handling Java switch constructs . Contributed-by: Vasanth Venkatachalam diff -r c0085eefbd42 -r f705fc04faa5 graal/com.oracle.graal.asm.hsail/src/com/oracle/graal/asm/hsail/HSAILAssembler.java --- a/graal/com.oracle.graal.asm.hsail/src/com/oracle/graal/asm/hsail/HSAILAssembler.java Wed Nov 20 22:40:27 2013 +0100 +++ b/graal/com.oracle.graal.asm.hsail/src/com/oracle/graal/asm/hsail/HSAILAssembler.java Wed Nov 20 22:50:39 2013 +0100 @@ -23,6 +23,8 @@ package com.oracle.graal.asm.hsail; +import java.lang.reflect.*; + import com.oracle.graal.api.code.*; import static com.oracle.graal.api.code.MemoryBarriers.*; @@ -75,23 +77,35 @@ } /** - * An Object is only moved into a register when it is a class constant (which is not really a - * constant because it can be moved by GC). Because we can't patch the HSAIL once it is - * finalized, we handle changes due to GC movement by dereferencing a global reference that is - * created by JNI since these JNI global references do not move. + * Moves an Object into a register. + * + * Because Object references become stale after Garbage collection (GC) the technique used here + * is to load a JNI global reference to that Object into the register. These JNI global + * references get updated by the GC whenever the GC moves an Object. + * + * @param a the destination register + * @param obj the Object being moved */ public final void mov(Register a, Object obj) { String regName = "$d" + a.encoding(); - if (obj instanceof Class) { - Class clazz = (Class) obj; - long refHandle = OkraUtil.getRefHandle(clazz); - String className = clazz.getName(); - emitString("mov_b64 " + regName + ", 0x" + Long.toHexString(refHandle) + "; // handle for " + className); - emitString("ld_global_u64 " + regName + ", [" + regName + "];"); - } else if (obj == null) { + // For a null object simply move 0x0 into the destination register. + if (obj == null) { emitString("mov_b64 " + regName + ", 0x0; // null object"); } else { - throw GraalInternalError.shouldNotReachHere("mov from object not a class"); + // Get a JNI reference handle to the object. + long refHandle = OkraUtil.getRefHandle(obj); + // Get the clasname of the object for emitting a comment. + Class clazz = obj.getClass(); + String className = clazz.getName(); + String comment = "// handle for object of type " + className; + // If the object is an array note the array length in the comment. + if (className.startsWith("[")) { + comment += ", length " + Array.getLength(obj); + } + // First move the reference handle into a register. + emitString("mov_b64 " + regName + ", 0x" + Long.toHexString(refHandle) + "; " + comment); + // Next load the Object addressed by this reference handle into the destination reg. + emitString("ld_global_u64 " + regName + ", [" + regName + "];"); } } @@ -247,9 +261,22 @@ return prefix; } + /** + * Emits a compare instruction. + * + * @param src0 - the first source register + * @param src1 - the second source register + * @param condition - the compare condition i.e., eq, ne, lt, gt + * @param unordered - flag specifying if this is an unordered compare. This only applies to + * float compares. + * @param isUnsignedCompare - flag specifying if this is a compare of unsigned values. + */ public void emitCompare(Value src0, Value src1, String condition, boolean unordered, boolean isUnsignedCompare) { + // Formulate the prefix of the instruction. String prefix = "cmp_" + condition + (unordered ? "u" : "") + "_b1_" + (isUnsignedCompare ? getArgTypeForceUnsigned(src1) : getArgType(src1)); + // Generate a comment for debugging purposes String comment = (isConstant(src1) && (src1.getKind() == Kind.Object) && (asConstant(src1).asObject() == null) ? " // null test " : ""); + // Emit the instruction. emitString(prefix + " $c0, " + mapRegOrConstToString(src0) + ", " + mapRegOrConstToString(src1) + ";" + comment); } diff -r c0085eefbd42 -r f705fc04faa5 graal/com.oracle.graal.compiler.hsail.test/src/com/oracle/graal/compiler/hsail/test/IntLookupSwitchTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.hsail.test/src/com/oracle/graal/compiler/hsail/test/IntLookupSwitchTest.java Wed Nov 20 22:50:39 2013 +0100 @@ -0,0 +1,124 @@ +/* + * Copyright (c) 2009, 2013, 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.compiler.hsail.test; + +import org.junit.Test; +import com.oracle.graal.compiler.hsail.test.infra.*; + +/** + * Tests a switch statement with integer keys. This test exercises the LOOKUPSWITCH Java bytecode + * instruction. + * + * The HSAIL code generated for this example is a series of cascading compare and branch + * instructions for each case of the switch. + * + * These HSAIL instructions have the following form: + * + * + * //Check whether the key matches the key constant of the case. Store the result of the compare (0 + * or 1) in the control register c0. + * + * cmp_eq $c0 , + * + * //Branch to the corresponding label of that case if there's a match. + * + * cbr $c0 + */ +public class IntLookupSwitchTest extends GraalKernelTester { + + static final int num = 20; + // Output array storing the results of the operations. + @Result protected int[] outArray = new int[num]; + + /** + * The static "kernel" method we will be testing. This method writes to an output array based on + * switching on an element of an input array. By convention the gid is the last parameter. + * + * Note: Because the key constants used in the cases of the switch are sparsely distributed, the + * Java source compiler compiles this example into the LOOKUPSWITCH bytecode instruction. So + * this is really a test to see whether the HSAIL backend is appropriately handling the + * LOOKUPSWITCH bytecode. + * + * @param out the output array + * @param ina the input array + * @param gid the parameter used to index into the input and output arrays + */ + public static void run(int[] out, int[] ina, int gid) { + switch (ina[gid]) { + case 0: + out[gid] = ina[gid]; + break; + case 1: + case 2: + break; + case 5: + out[gid] = ina[gid] * ina[gid]; + break; + case 10: + out[gid] = -ina[gid]; + break; + case 15: + out[gid] = ina[gid] - ina[gid]; + break; + case 19: + out[gid] = ina[gid] + ina[gid]; + break; + default: + out[gid] = 9; + break; + } + out[gid] += ina[gid]; + } + + /** + * Tests the HSAIL code generated for this unit test by comparing the result of executing this + * code with the result of executing a sequential Java version of this unit test. + */ + @Test + public void test() { + super.testGeneratedHsail(); + } + + /** + * Initializes the input and output arrays passed to the run routine. + * + * @param in the input array + */ + void setupArrays(int[] in) { + for (int i = 0; i < num; i++) { + in[i] = i < num / 2 ? i : -i; + outArray[i] = 0; + } + } + + /** + * Dispatches the HSAIL kernel for this test case. + */ + @Override + public void runTest() { + int[] inArray = new int[num]; + setupArrays(inArray); + dispatchMethodKernel(num, outArray, inArray); + } +} diff -r c0085eefbd42 -r f705fc04faa5 graal/com.oracle.graal.compiler.hsail.test/src/com/oracle/graal/compiler/hsail/test/IntTableSwitchTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.hsail.test/src/com/oracle/graal/compiler/hsail/test/IntTableSwitchTest.java Wed Nov 20 22:50:39 2013 +0100 @@ -0,0 +1,137 @@ +/* + * Copyright (c) 2009, 2013, 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.compiler.hsail.test; + +import org.junit.Test; +import com.oracle.graal.compiler.hsail.test.infra.*; + +/** + * Tests a switch statement with integer keys. This test exercises the TABLESWITCH Java bytecode + * instruction. + * + * The HSAIL code generated for this example is a series of cascading compare and branch + * instructions for each case of the switch. + * + * These instruction have the following form: + * + * + * //Check whether the key matches the key constant of the case. Store the result of the compare (0 + * or 1) in the control register c0. + * + * cmp_eq $c0 , + * + * //Branch to the corresponding label of that case if there's a match. + * + * cbr $c0 + */ +public class IntTableSwitchTest extends GraalKernelTester { + + static final int num = 20; + // Output array storing the results of the operations. + @Result protected int[] outArray = new int[num]; + + /** + * The static "kernel" method we will be testing. This method writes to an output array based on + * switching on an element of an input array. + * + * Note: Because the key constants used in the cases of the switch are in consecutive order, the + * Java source compiler compiles this example into the TABLESWITCH bytecode instruction. So this + * is really a test to see whether the HSAIL backend is appropriately handling the TABLESWITCH + * bytecode. + * + * @param out the output array + * @param ina the input array + * @param gid the parameter used to index into the input and output arrays + */ + public static void run(int[] out, int[] ina, int gid) { + switch (ina[gid]) { + case 0: + out[gid] = ina[gid]; + break; + case 1: + out[gid] = ina[gid] * ina[gid]; + break; + case 2: + out[gid] = -ina[gid]; + break; + case 3: + out[gid] = ina[gid] - ina[gid]; + break; + case 4: + out[gid] = ina[gid] + ina[gid]; + break; + case 5: + case 6: + out[gid] = ina[gid] * ina[gid]; + break; + case 7: + out[gid] = -ina[gid] * 7; + break; + case 8: + break; + case 9: + int i = ina[gid] * 5; + out[gid] = ina[gid] - ina[gid] + i; + break; + case 10: + out[gid] = ina[gid] + ina[gid]; + break; + default: + out[gid] = 9; + break; + } + out[gid] += ina[gid]; + } + + /** + * Tests the HSAIL code generated for this unit test by comparing the result of executing this + * code with the result of executing a sequential Java version of this unit test. + */ + @Test + public void test() { + super.testGeneratedHsail(); + } + + /** + * Initializes the input and output arrays passed to the run routine. + * + * @param in the input array + */ + void setupArrays(int[] in) { + for (int i = 0; i < num; i++) { + in[i] = i < num / 2 ? i : -i; + outArray[i] = 0; + } + } + + /** + * Dispatches the HSAIL kernel for this test case. + */ + @Override + public void runTest() { + int[] inArray = new int[num]; + setupArrays(inArray); + dispatchMethodKernel(num, outArray, inArray); + } +} diff -r c0085eefbd42 -r f705fc04faa5 graal/com.oracle.graal.compiler.hsail.test/src/com/oracle/graal/compiler/hsail/test/StringSwitchTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.hsail.test/src/com/oracle/graal/compiler/hsail/test/StringSwitchTest.java Wed Nov 20 22:50:39 2013 +0100 @@ -0,0 +1,156 @@ +/* + * Copyright (c) 2009, 2013, 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.compiler.hsail.test; + +import static org.junit.Assume.*; + +import org.junit.Test; +import com.oracle.graal.compiler.hsail.test.infra.*; + +/** + * Tests switch statement with String literal keys. + * + * Note: In Java bytecode, this example reduces to a LOOKUPSWITCH over int keys because the Java + * source compiler generates a call to String.hashcode( ) to convert to int values. + * + * The HSAIL code generated for this example is a series of cascading compare and branch + * instructions for each case of the switch. + * + * These instruction have the following form: + * + * + * //Check whether the key matches the key constant of the case. Store the result of the compare (0 + * or 1) in the control register c0. + * + * cmp_eq $c0 , + * + * //Branch to the corresponding label of that case if there's a match. + * + * cbr $c0 + */ +public class StringSwitchTest extends GraalKernelTester { + + static final int num = 40; + // Output array storing the results of the operations. + @Result protected int[] outArray = new int[num]; + + // Array of Strings + String[] names = {"0-42L", "0-43-", "Mazda", "Nissan", "Chevrolet", "Porsche", "Ford Focus", "Volvo", "Cadillac", "BMW", "Indy Car", "Police Car", "Lexus", "Datsun", "Saab", "Volkswagen", + "Honda Civic", "Jeeo Wrangler", "Toyota", "Mustang", "Chrysler", "Subaru"}; + + /** + * The static "kernel" method we will be testing. This method performs a switch statement over a + * String literal key. + * + * @param out the output array + * @param ina the input array of String literal keys + * @param gid the parameter used to index into the input and output arrays + */ + public static void run(int[] out, String[] ina, int gid) { + switch (ina[gid]) { + case "Mazda": + out[gid] = 1; + break; + case "Nissan": + out[gid] = 2; + break; + case "Chevrolet": + out[gid] = 3; + break; + case "Porsche": + out[gid] = 4; + break; + case "Jeep Wrangler": + out[gid] = 5; + break; + case "Toyota": + out[gid] = 6; + break; + case "0-42L": + out[gid] = 890; + break; + case "0-43-": + out[gid] = 995; + break; + case "Chrysler": + out[gid] = 7; + break; + case "Mitsubishi": + out[gid] = 8; + break; + case "Ford Focus": + out[gid] = 9; + break; + case "Volvo": + out[gid] = 10; + break; + case "Subaru": + out[gid] = 11; + break; + case "BMW": + out[gid] = 12; + break; + case "Indy Car": + out[gid] = 13; + break; + case "Police Car": + out[gid] = 14; + break; + } + } + + /** + * Tests the HSAIL code generated for this unit test by comparing the result of executing this + * code with the result of executing a sequential Java version of this unit test. + */ + @Test + public void test() { + // This test is only run if inlining is enabled since it requires method call support. + assumeTrue(aggressiveInliningEnabled() || canHandleHSAILMethodCalls()); + super.testGeneratedHsail(); + } + + /** + * Initializes the input and output arrays passed to the run routine. + * + * @param in the input array + */ + void setupArrays(String[] in) { + for (int i = 0; i < num; i++) { + // fill the input array with Strings. + in[i] = names[i % names.length]; + outArray[i] = 0; + } + } + + /** + * Dispatches the HSAIL kernel for this test case. + */ + @Override + public void runTest() { + String[] inArray = new String[num]; + setupArrays(inArray); + dispatchMethodKernel(num, outArray, inArray); + } +} diff -r c0085eefbd42 -r f705fc04faa5 graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java --- a/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java Wed Nov 20 22:40:27 2013 +0100 +++ b/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java Wed Nov 20 22:50:39 2013 +0100 @@ -47,12 +47,14 @@ import com.oracle.graal.lir.hsail.HSAILControlFlow.FloatCompareBranchOp; import com.oracle.graal.lir.hsail.HSAILControlFlow.FloatCondMoveOp; import com.oracle.graal.lir.hsail.HSAILControlFlow.ReturnOp; +import com.oracle.graal.lir.hsail.HSAILControlFlow.SwitchOp; import com.oracle.graal.lir.hsail.HSAILMove.LeaOp; import com.oracle.graal.lir.hsail.HSAILMove.MembarOp; import com.oracle.graal.lir.hsail.HSAILMove.MoveFromRegOp; import com.oracle.graal.lir.hsail.HSAILMove.MoveToRegOp; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.extended.*; import com.oracle.graal.phases.util.*; /** @@ -688,9 +690,61 @@ append(new ReturnOp(input)); } + /** + * This routine handles the LIR code generation for switch nodes by calling + * emitSequentialSwitch. + * + * This routine overrides LIRGenerator.emitSwitch( ) which calls emitSequentialSwitch or + * emitTableSwitch based on a heuristic. + * + * The recommended approach in HSAIL for generating performant code for switch statements is to + * emit a series of cascading compare and branches. Thus this routines always calls + * emitSequentialSwitch, which implements this approach. + * + * Note: Only IntegerSwitchNodes are currently supported. The IntegerSwitchNode is the node that + * Graal generates for any switch construct appearing in Java bytecode. + * + * @param x the SwitchNode + */ + @Override + public void emitSwitch(SwitchNode x) { + // get the key of the switch. + Variable key = load(operand(x.value())); + // set the default target. + LabelRef defaultTarget = x.defaultSuccessor() == null ? null : getLIRBlock(x.defaultSuccessor()); + // emit a sequential switch for the specified key and default target. + emitSequentialSwitch(x, key, defaultTarget); + } + + /** + * Generates the LIR instruction for a switch construct that is meant to be assembled into a + * series of cascading compare and branch instructions. This is currently the recommended way of + * generating performant HSAIL code for switch constructs. + * + * In Java bytecode the keys for switch statements are always ints. + * + * The x86 backend also adds support for handling keys of type long or Object but these two + * special cases are for handling the TypeSwitchNode, which is a node that the JVM produces for + * handling operations related to method dispatch. We haven't yet added support for the + * TypeSwitchNode, so for the time being we have added a check to ensure that the keys are of + * type int. This also allows us to flag any test cases/execution paths that may trigger the + * creation fo a TypeSwitchNode which we don't support yet. + * + * + * @param keyConstants array of key constants used for the case statements. + * @param keyTargets array of branch targets for each of the cases. + * @param defaultTarget the branch target for the default case. + * @param key the key that is compared against the key constants in the case statements. + */ @Override protected void emitSequentialSwitch(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { - throw GraalInternalError.unimplemented(); + if (key.getKind() == Kind.Int) { + // Append the LIR instruction for generating compare and branch instructions. + append(new SwitchOp(keyConstants, keyTargets, defaultTarget, key)); + } else { + // Throw an exception if the keys aren't ints. + throw GraalInternalError.unimplemented("Switch statements are only supported for keys of type int"); + } } @Override diff -r c0085eefbd42 -r f705fc04faa5 graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILControlFlow.java --- a/graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILControlFlow.java Wed Nov 20 22:40:27 2013 +0100 +++ b/graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILControlFlow.java Wed Nov 20 22:50:39 2013 +0100 @@ -28,6 +28,7 @@ import com.oracle.graal.asm.hsail.*; import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.FallThroughOp; import com.oracle.graal.lir.asm.*; import com.oracle.graal.nodes.calc.*; @@ -36,6 +37,96 @@ */ public class HSAILControlFlow { + /** + * This class represents the LIR instruction that the HSAIL backend generates for a switch + * construct in Java. + * + * The HSAIL backend compiles switch statements into a series of cascading compare and branch + * instructions because this is the currently the recommended way to generate optimally + * performing HSAIL code. Thus the execution path for both the TABLESWITCH and LOOKUPSWITCH + * bytecodes go through this op. + */ + public static class SwitchOp extends HSAILLIRInstruction implements FallThroughOp { + /** + * The array of key constants used for the cases of this switch statement. + */ + @Use({CONST}) protected Constant[] keyConstants; + /** + * The branch target labels that correspond to each case. + */ + private final LabelRef[] keyTargets; + private LabelRef defaultTarget; + /** + * The key of the switch. This will be compared with each of the keyConstants. + */ + @Alive({REG}) protected Value key; + + /** + * Constructor. Called from the HSAILLIRGenerator.emitSequentialSwitch routine. + * + * @param keyConstants + * @param keyTargets + * @param defaultTarget + * @param key + */ + public SwitchOp(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { + assert keyConstants.length == keyTargets.length; + this.keyConstants = keyConstants; + this.keyTargets = keyTargets; + this.defaultTarget = defaultTarget; + this.key = key; + } + + /** + * Get the default target for this switch op. + */ + @Override + public LabelRef fallThroughTarget() { + return defaultTarget; + } + + /** + * Set the default target. + * + * @param target the default target + */ + @Override + public void setFallThroughTarget(LabelRef target) { + defaultTarget = target; + + } + + /** + * Generates the code for this switch op. + * + * The keys for switch statements in Java bytecode for of type int. However, Graal also + * generates a TypeSwitchNode (for method dispatch) which triggers the invocation of these + * routines with keys of type Long or Object. Currently we only support the + * IntegerSwitchNode so we throw an exception if the key isn't of type int. + * + * @param tasm the TargetMethodAssembler + * @param masm the HSAIL assembler + */ + @Override + public void emitCode(TargetMethodAssembler tasm, HSAILAssembler masm) { + if (key.getKind() == Kind.Int) { + for (int i = 0; i < keyConstants.length; i++) { + // Generate cascading compare and branches for each case. + masm.emitCompare(key, keyConstants[i], "eq", false, false); + masm.cbr(masm.nameOf(keyTargets[i].label())); + } + // Generate a jump for the default target if there is one. + if (defaultTarget != null) { + masm.jmp(defaultTarget.label()); + } + + } else { + // Throw an exception if the key isn't of type int. + throw new GraalInternalError("Switch statments are only supported for int keys"); + } + } + } + public static class ReturnOp extends HSAILLIRInstruction { @Use({REG, ILLEGAL}) protected Value x;