From d2af79a77ed2936ff0ed90cadf8e48637d774d4c Mon Sep 17 00:00:00 2001 From: Xavier Leroy Date: Tue, 4 Oct 2016 15:52:16 +0200 Subject: Turn 64-bit integer division and modulus by constants into multiply-high This trick was already implemented for 32-bit integer division and modulus. Here we extend it to the 64-bit case. For 32-bit target processors, the runtime library must implement 64-bit multiply-high (signed and unsigned). Tentative implementations are provided for IA32 and PowerPC, but need testing. --- runtime/c/i64.h | 2 ++ runtime/c/i64_smulh.c | 56 +++++++++++++++++++++++++++++++++++++++++++ runtime/c/i64_umulh.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 124 insertions(+) create mode 100644 runtime/c/i64_smulh.c create mode 100644 runtime/c/i64_umulh.c (limited to 'runtime/c') diff --git a/runtime/c/i64.h b/runtime/c/i64.h index dd584533..a75214fe 100644 --- a/runtime/c/i64.h +++ b/runtime/c/i64.h @@ -41,3 +41,5 @@ extern signed long long __i64_sar(signed long long x, int amount); extern unsigned long long __i64_udivmod(unsigned long long n, unsigned long long d, unsigned long long * rp); +extern unsigned long long __i64_umulh(unsigned long long u, + unsigned long long v); diff --git a/runtime/c/i64_smulh.c b/runtime/c/i64_smulh.c new file mode 100644 index 00000000..b7a42474 --- /dev/null +++ b/runtime/c/i64_smulh.c @@ -0,0 +1,56 @@ +/***************************************************************** + * + * The Compcert verified compiler + * + * Xavier Leroy, INRIA Paris-Rocquencourt + * + * Copyright (c) 2013 Institut National de Recherche en Informatique et + * en Automatique. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of the nor the + * names of its contributors may be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + **********************************************************************/ + +/* Helper functions for 64-bit integer arithmetic. Reference C implementation */ + +#include "i64.h" + +typedef signed long long s64; +typedef unsigned long long u64; + +/* Signed multiply high */ + +/* Hacker's Delight section 8.3: + * - compute high 64 bits of the unsigned product X * Y + * - subtract X if Y < 0 + * - subtract Y if X < 0 + */ + +s64 __i64_smulh(s64 x, s64 y) +{ + s64 t = (s64) __i64_umulh(x, y); + if (y < 0) t = t - x; + if (x < 0) t = t - y; + return t; +} diff --git a/runtime/c/i64_umulh.c b/runtime/c/i64_umulh.c new file mode 100644 index 00000000..d2394d09 --- /dev/null +++ b/runtime/c/i64_umulh.c @@ -0,0 +1,66 @@ +/***************************************************************** + * + * The Compcert verified compiler + * + * Xavier Leroy, INRIA Paris + * + * Copyright (c) 2016 Institut National de Recherche en Informatique et + * en Automatique. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of the nor the + * names of its contributors may be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + **********************************************************************/ + +/* Helper functions for 64-bit integer arithmetic. Reference C implementation */ + +#include "i64.h" + +typedef unsigned long long u64; +typedef unsigned int u32; + +/* Unsigned multiply high */ + +/* Hacker's Delight, algorithm 8.1, specialized to two 32-bit words */ + +u64 __i64_umulh(u64 u, u64 v) +{ + u32 u0 = u, u1 = u >> 32; + u32 v0 = v, v1 = v >> 32; + u32 w1, w2, w3, k; + u64 t; + + t = (u64) u0 * (u64) v0; + k = t >> 32; + + t = (u64) u1 * (u64) v0 + k; + w1 = t; + w2 = t >> 32; + + t = (u64) u0 * (u64) v1 + w1; + k = t >> 32; + + t = (u64) u1 * (u64) v1 + w2 + k; + + return t; +} -- cgit