# HG changeset patch # User twisti # Date 1234544975 28800 # Node ID bbef4344adb2b076fbaa15728526ecb56be72246 # Parent 91263420e1c63420603fa891c12bd7da4ea2bf6f 6800154: Add comments to long_by_long_mulhi() for better understandability Summary: This patch adds a comment pointing to the Hacker's Delight version of the algorithm plus a verbatim copy of it. Furthermore it adds inline comments. Reviewed-by: kvn, jrose diff -r 91263420e1c6 -r bbef4344adb2 src/share/vm/opto/divnode.cpp --- a/src/share/vm/opto/divnode.cpp Fri Feb 06 13:31:03 2009 -0800 +++ b/src/share/vm/opto/divnode.cpp Fri Feb 13 09:09:35 2009 -0800 @@ -1,5 +1,5 @@ /* - * Copyright 1997-2008 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 1997-2009 Sun Microsystems, Inc. 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 @@ -244,42 +244,73 @@ //---------------------long_by_long_mulhi-------------------------------------- // Generate ideal node graph for upper half of a 64 bit x 64 bit multiplication -static Node *long_by_long_mulhi( PhaseGVN *phase, Node *dividend, jlong magic_const) { +static Node* long_by_long_mulhi(PhaseGVN* phase, Node* dividend, jlong magic_const) { // If the architecture supports a 64x64 mulhi, there is // no need to synthesize it in ideal nodes. if (Matcher::has_match_rule(Op_MulHiL)) { - Node *v = phase->longcon(magic_const); + Node* v = phase->longcon(magic_const); return new (phase->C, 3) MulHiLNode(dividend, v); } + // Taken from Hacker's Delight, Fig. 8-2. Multiply high signed. + // (http://www.hackersdelight.org/HDcode/mulhs.c) + // + // int mulhs(int u, int v) { + // unsigned u0, v0, w0; + // int u1, v1, w1, w2, t; + // + // u0 = u & 0xFFFF; u1 = u >> 16; + // v0 = v & 0xFFFF; v1 = v >> 16; + // w0 = u0*v0; + // t = u1*v0 + (w0 >> 16); + // w1 = t & 0xFFFF; + // w2 = t >> 16; + // w1 = u0*v1 + w1; + // return u1*v1 + w2 + (w1 >> 16); + // } + // + // Note: The version above is for 32x32 multiplications, while the + // following inline comments are adapted to 64x64. + const int N = 64; - Node *u_hi = phase->transform(new (phase->C, 3) RShiftLNode(dividend, phase->intcon(N / 2))); - Node *u_lo = phase->transform(new (phase->C, 3) AndLNode(dividend, phase->longcon(0xFFFFFFFF))); + // u0 = u & 0xFFFFFFFF; u1 = u >> 32; + Node* u0 = phase->transform(new (phase->C, 3) AndLNode(dividend, phase->longcon(0xFFFFFFFF))); + Node* u1 = phase->transform(new (phase->C, 3) RShiftLNode(dividend, phase->intcon(N / 2))); + + // v0 = v & 0xFFFFFFFF; v1 = v >> 32; + Node* v0 = phase->longcon(magic_const & 0xFFFFFFFF); + Node* v1 = phase->longcon(magic_const >> (N / 2)); - Node *v_hi = phase->longcon(magic_const >> N/2); - Node *v_lo = phase->longcon(magic_const & 0XFFFFFFFF); + // w0 = u0*v0; + Node* w0 = phase->transform(new (phase->C, 3) MulLNode(u0, v0)); - Node *hihi_product = phase->transform(new (phase->C, 3) MulLNode(u_hi, v_hi)); - Node *hilo_product = phase->transform(new (phase->C, 3) MulLNode(u_hi, v_lo)); - Node *lohi_product = phase->transform(new (phase->C, 3) MulLNode(u_lo, v_hi)); - Node *lolo_product = phase->transform(new (phase->C, 3) MulLNode(u_lo, v_lo)); + // t = u1*v0 + (w0 >> 32); + Node* u1v0 = phase->transform(new (phase->C, 3) MulLNode(u1, v0)); + Node* temp = phase->transform(new (phase->C, 3) URShiftLNode(w0, phase->intcon(N / 2))); + Node* t = phase->transform(new (phase->C, 3) AddLNode(u1v0, temp)); + + // w1 = t & 0xFFFFFFFF; + Node* w1 = new (phase->C, 3) AndLNode(t, phase->longcon(0xFFFFFFFF)); - Node *t1 = phase->transform(new (phase->C, 3) URShiftLNode(lolo_product, phase->intcon(N / 2))); - Node *t2 = phase->transform(new (phase->C, 3) AddLNode(hilo_product, t1)); + // w2 = t >> 32; + Node* w2 = new (phase->C, 3) RShiftLNode(t, phase->intcon(N / 2)); + + // 6732154: Construct both w1 and w2 before transforming, so t + // doesn't go dead prematurely. + w1 = phase->transform(w1); + w2 = phase->transform(w2); - // Construct both t3 and t4 before transforming so t2 doesn't go dead - // prematurely. - Node *t3 = new (phase->C, 3) RShiftLNode(t2, phase->intcon(N / 2)); - Node *t4 = new (phase->C, 3) AndLNode(t2, phase->longcon(0xFFFFFFFF)); - t3 = phase->transform(t3); - t4 = phase->transform(t4); + // w1 = u0*v1 + w1; + Node* u0v1 = phase->transform(new (phase->C, 3) MulLNode(u0, v1)); + w1 = phase->transform(new (phase->C, 3) AddLNode(u0v1, w1)); - Node *t5 = phase->transform(new (phase->C, 3) AddLNode(t4, lohi_product)); - Node *t6 = phase->transform(new (phase->C, 3) RShiftLNode(t5, phase->intcon(N / 2))); - Node *t7 = phase->transform(new (phase->C, 3) AddLNode(t3, hihi_product)); + // return u1*v1 + w2 + (w1 >> 32); + Node* u1v1 = phase->transform(new (phase->C, 3) MulLNode(u1, v1)); + Node* temp1 = phase->transform(new (phase->C, 3) AddLNode(u1v1, w2)); + Node* temp2 = phase->transform(new (phase->C, 3) RShiftLNode(w1, phase->intcon(N / 2))); - return new (phase->C, 3) AddLNode(t7, t6); + return new (phase->C, 3) AddLNode(temp1, temp2); } diff -r 91263420e1c6 -r bbef4344adb2 test/compiler/6603011/Test.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/6603011/Test.java Fri Feb 13 09:09:35 2009 -0800 @@ -0,0 +1,220 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +/** + * @test + * @bug 6603011 + * @summary long/int division by constant + * + * @run main/othervm -Xcomp -Xbatch -XX:-Inline Test + */ + +// +// -XX:-Inline is essential to this test so that verification functions +// divi, modi, divl and modl generate "plain" divides. +// -Xcomp -Xbatch are also useful to ensure the full range of +// dividend and divisor combinations are tested +// + +import java.net.*; + +class s { + static int divi(int dividend, int divisor) { return dividend / divisor; } + static int modi(int dividend, int divisor) { return dividend % divisor; } + static long divl(long dividend, long divisor) { return dividend / divisor; } + static long modl(long dividend, long divisor) { return dividend % divisor; } +} + +public class Test implements Runnable { + // Report verbose messages on failure; turn off to suppress + // too much output with gross numbers of failures. + static final boolean VERBOSE = true; + + // Initailize DIVISOR so that it is final in this class. + static final int DIVISOR; + static { + int value = 0; + try { + value = Integer.decode(System.getProperty("divisor")); + } catch (Throwable e) { + } + DIVISOR = value; + } + + // The methods of interest. We want the JIT to compile these + // and convert the divide into a multiply. + public int divbyI (int dividend) { return dividend / DIVISOR; } + public int modbyI (int dividend) { return dividend % DIVISOR; } + public long divbyL (long dividend) { return dividend / DIVISOR; } + public long modbyL (long dividend) { return dividend % DIVISOR; } + + public int divisor() { return DIVISOR; } + + public boolean checkI (int dividend) { + int quo = divbyI(dividend); + int rem = modbyI(dividend); + int quo0 = s.divi(dividend, divisor()); + int rem0 = s.modi(dividend, divisor()); + + if (quo != quo0 || rem != rem0) { + if (VERBOSE) { + System.out.println("Computed: " + dividend + " / " + divisor() + " = " + + quo + ", " + dividend + " % " + divisor() + " = " + rem ); + System.out.println("expected: " + dividend + " / " + divisor() + " = " + + quo0 + ", " + dividend + " % " + divisor() + " = " + rem0); + // Report sign of rem failure + if (rem != 0 && (rem ^ dividend) < 0) { + System.out.println(" rem & dividend have different signs"); + } + // Report range of rem failure + if (java.lang.Math.abs(rem) >= java.lang.Math.abs(divisor())) { + System.out.println(" remainder out of range"); + } + // Report quo/rem identity relationship failure + if ((quo * divisor()) + rem != dividend) { + System.out.println(" quotien/remainder invariant broken"); + } + } + return false; + } + return true; + } + + public boolean checkL (long dividend) { + long quo = divbyL(dividend); + long rem = modbyL(dividend); + long quo0 = s.divl(dividend, divisor()); + long rem0 = s.modl(dividend, divisor()); + + if (quo != quo0 || rem != rem0) { + if (VERBOSE) { + System.out.println(" " + dividend + " / " + divisor() + " = " + + quo + ", " + dividend + " % " + divisor() + " = " + rem); + // Report sign of rem failure + if (rem != 0 && (rem ^ dividend) < 0) { + System.out.println(" rem & dividend have different signs"); + } + // Report range of rem failure + if (java.lang.Math.abs(rem) >= java.lang.Math.abs(divisor())) { + System.out.println(" remainder out of range"); + } + // Report quo/rem identity relationship failure + if ((quo * divisor()) + rem != dividend) { + System.out.println(" (" + quo + " * " + divisor() + ") + " + rem + " != " + + dividend); + } + } + return false; + } + return true; + } + + public void run() { + // Don't try to divide by zero + if (divisor() == 0) return; + + // Range of dividends to check. Try dividends from start to end + // inclusive, as well as variations on those values as shifted + // left. + int start = -1024; + int end = 1024; + + // Test int division using a variety of dividends. + int wrong = 0; + int total = 0; + + outerloop: + for (int i = start; i <= end; i++) { + for (int s = 0; s < 32; s += 4) { + total++; + int dividend = i << s; + if (!checkI(dividend)) { + wrong++; + // Stop on the first failure + // break outerloop; + } + } + } + if (wrong > 0) { + System.out.println("divisor " + divisor() + ": " + + wrong + "/" + total + " wrong int divisions"); + } + + // Test long division using a variety of dividends. + wrong = 0; + total = 0; + + outerloop: + for (int i = start; i <= end; i++) { + for (int s = 0; s < 64; s += 4) { + total++; + long dividend = i << s; + if (!checkL(dividend)) { + wrong++; + // Stop on the first failure + // break outerloop; + } + } + } + if (wrong > 0) { + System.out.println("divisor " + divisor() + ": " + + wrong + "/" + total + " wrong long divisions"); + } + + } + + // Reload this class with the "divisor" property set to the input parameter. + // This allows the JIT to see q.DIVISOR as a final constant, and change + // any divisions or mod operations into multiplies. + public static void test_divisor(int divisor, + URLClassLoader apploader) throws Exception { + System.setProperty("divisor", "" + divisor); + ClassLoader loader = new URLClassLoader(apploader.getURLs(), + apploader.getParent()); + Class c = loader.loadClass("Test"); + Runnable r = (Runnable)c.newInstance(); + r.run(); + } + + public static void main(String[] args) throws Exception { + Class cl = Class.forName("Test"); + URLClassLoader apploader = (URLClassLoader)cl.getClassLoader(); + + + // Test every divisor between -100 and 100. + for (int i = -100; i <= 100; i++) { + test_divisor(i, apploader); + } + + // Try a few divisors outside the typical range. + // The values below have been observed in rt.jar. + test_divisor(101, apploader); + test_divisor(400, apploader); + test_divisor(1000, apploader); + test_divisor(3600, apploader); + test_divisor(9973, apploader); + test_divisor(86400, apploader); + test_divisor(1000000, apploader); + } + +} diff -r 91263420e1c6 -r bbef4344adb2 test/compiler/6800154/Test6800154.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/6800154/Test6800154.java Fri Feb 13 09:09:35 2009 -0800 @@ -0,0 +1,109 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +/** + * @test + * @bug 6800154 + * @summary Add comments to long_by_long_mulhi() for better understandability + * + * @run main/othervm -Xcomp -XX:CompileOnly=Test6800154.divcomp Test6800154 + */ + +import java.net.URLClassLoader; + +public class Test6800154 implements Runnable { + static final long[] DIVIDENDS = { + 0, + 1, + 2, + 1423487, + 4444441, + 4918923241323L, + -1, + -24351, + 0x3333, + 0x0000000080000000L, + 0x7fffffffffffffffL, + 0x8000000000000000L + }; + + static final long[] DIVISORS = { + 1, + 2, + 17, + 12342, + 24123, + 143444, + 123444442344L, + -1, + -2, + -4423423234231423L, + 0x0000000080000000L, + 0x7fffffffffffffffL, + 0x8000000000000000L + }; + + // Initialize DIVISOR so that it is final in this class. + static final long DIVISOR; + + static { + long value = 0; + try { + value = Long.decode(System.getProperty("divisor")); + } catch (Throwable e) { + } + DIVISOR = value; + } + + public static void main(String[] args) throws Exception + { + Class cl = Class.forName("Test6800154"); + URLClassLoader apploader = (URLClassLoader) cl.getClassLoader(); + + // Iterate over all divisors. + for (int i = 0; i < DIVISORS.length; i++) { + System.setProperty("divisor", "" + DIVISORS[i]); + ClassLoader loader = new URLClassLoader(apploader.getURLs(), apploader.getParent()); + Class c = loader.loadClass("Test6800154"); + Runnable r = (Runnable) c.newInstance(); + r.run(); + } + } + + public void run() + { + // Iterate over all dividends. + for (int i = 0; i < DIVIDENDS.length; i++) { + long dividend = DIVIDENDS[i]; + + long expected = divint(dividend); + long result = divcomp(dividend); + + if (result != expected) + throw new InternalError(dividend + " / " + DIVISOR + " failed: " + result + " != " + expected); + } + } + + static long divint(long a) { return a / DIVISOR; } + static long divcomp(long a) { return a / DIVISOR; } +}