Author: zhuqing
Date: 2011-08-08 03:47:30 -0400 (Mon, 08 Aug 2011)
New Revision: 3711
Modified:
trunk/osprey/be/cg/ia64/exp_divrem.cxx
trunk/osprey/be/cg/x8664/exp_divrem.cxx
trunk/osprey/be/lno/x8664/lnotarget.cxx
Log:
Fix integer division simplification bug.
For case:
//opencc -O0, result is 1.
//opencc -O1, reuslt is 0.
unsigned long long a;
unsigned long long foo()
{
return a/-27ULL;
}
int main() {
a = -27ULL;
return foo();
}
When integer divisor is constant, Convert_WHIRL_To_OPs can simplfy it into
multiply and shift.
It invokes determine_pseudo_inverse to calculate the pseudo inverse and shift
bits.
In determine_pseudo_inverse
First step is calculates n for constant divisor b.
Smallest n, 2^n >= b and m = 2^n - 1.
Second step is calculate pseudo inversor d = 1 + (2^(n+maxbits_a) - 1) / b
The division is performed by loop shift and subtraction, because
2^(n+maxbits_a)-1 may exceed 64 bit.
Both m,b,q is UINT64.
m = 2^n-1
for(q=i=0; i<=maxbits_a; i++) {
q <<= 1;
if(m >= b) {
m -= b;
q |= 1;
}
m = (m<<1) | 1;
}
This implementation doesn't consider the case that (m<<1) | 1 may overflow when
b's 64 bit MSB is 1.
(m<<1) | 1 overflows means next iteration m's actual value must bigger than b
and should perform subtraction.
Fix is:
1. Record if m = (m<<1) | 1 overflow.
2. If m is overflow in previous iteration, perform subtraction.
Make the fix in IA and X8664, this problem may also exist on other platforms.
Code Review: Jian-Xin
Modified: trunk/osprey/be/cg/ia64/exp_divrem.cxx
===================================================================
--- trunk/osprey/be/cg/ia64/exp_divrem.cxx 2011-08-05 11:43:36 UTC (rev
3710)
+++ trunk/osprey/be/cg/ia64/exp_divrem.cxx 2011-08-08 07:47:30 UTC (rev
3711)
@@ -2141,12 +2141,31 @@
* d if maxbits_a < BPUL (bits per unsigned long)
* d-2^BPUL if maxbits_a == BPUL (i.e., all but top bit)
*/
+ BOOL m_overflow = FALSE;
for(q=i=0; i<=maxbits_a; i++) {
q <<= 1;
- if(m >= b) {
+ if(m_overflow) {
+ // because ((m>>1) | 0x8000000000000000ULL) >= m
+ // if m>=b in this iteration, then in last iteration m also >= b.
+ // This can't happen
+ Is_True(m < b, ("m bigger than b and m is overflow in last
iteration\n"));
m -= b;
q |= 1;
+ m_overflow = FALSE;
}
+ else if(m >= b) {
+ m -= b;
+ q |= 1;
+ }
+ // After subtraction, m must be smaller than b. And m's 64 bit MSB must be
zero.
+ // if m's 64bit MSB is 1, then subtraction not happen in this iteration.
+ // it means b>m, then b's 64 bit MSB is also 1.
+ // Mark m overflow and in next iteration, actually m is bigger than b.
+ // Need do subtraction in next itration.
+ if (m & 0x8000000000000000ULL) {
+ Is_True(b & 0x8000000000000000ULL, ("b's 64th bit must be 1\n"));
+ m_overflow = TRUE;
+ }
m = (m<<1) | 1;
}
return 1+q;
Modified: trunk/osprey/be/cg/x8664/exp_divrem.cxx
===================================================================
--- trunk/osprey/be/cg/x8664/exp_divrem.cxx 2011-08-05 11:43:36 UTC (rev
3710)
+++ trunk/osprey/be/cg/x8664/exp_divrem.cxx 2011-08-08 07:47:30 UTC (rev
3711)
@@ -239,12 +239,31 @@
* d if maxbits_a < BPUL (bits per unsigned long)
* d-2^BPUL if maxbits_a == BPUL (i.e., all but top bit)
*/
+ BOOL m_overflow = FALSE;
for(q=i=0; i<=maxbits_a; i++) {
q <<= 1;
- if(m >= b) {
+ if(m_overflow) {
+ // because ((m>>1) | 0x8000000000000000ULL) >= m
+ // if m>=b in this iteration, then in last iteration m also >= b.
+ // This can't happen
+ Is_True(m < b, ("m bigger than b and m is overflow in last
iteration\n"));
m -= b;
q |= 1;
+ m_overflow = FALSE;
}
+ else if(m >= b) {
+ m -= b;
+ q |= 1;
+ }
+ // After subtraction, m must be smaller than b. And m's 64 bit MSB must be
zero.
+ // if m's 64bit MSB is 1, then subtraction not happen in this iteration.
+ // it means b>m, then b's 64 bit MSB is also 1.
+ // Mark m overflow and in next iteration, actually m is bigger than b.
+ // Need do subtraction in next itration.
+ if (m & 0x8000000000000000ULL) {
+ Is_True(b & 0x8000000000000000ULL, ("b's 64th bit must be 1\n"));
+ m_overflow = TRUE;
+ }
m = (m<<1) | 1;
}
return 1+q;
Modified: trunk/osprey/be/lno/x8664/lnotarget.cxx
===================================================================
--- trunk/osprey/be/lno/x8664/lnotarget.cxx 2011-08-05 11:43:36 UTC (rev
3710)
+++ trunk/osprey/be/lno/x8664/lnotarget.cxx 2011-08-08 07:47:30 UTC (rev
3711)
@@ -1055,12 +1055,31 @@
* d if maxbits_a < BPUL (bits per unsigned long)
* d-2^BPUL if maxbits_a == BPUL (i.e., all but top bit)
*/
+ BOOL m_overflow = FALSE;
for(q=i=0; i<=maxbits_a; i++) {
q <<= 1;
- if(m >= b) {
+ if(m_overflow) {
+ // because ((m>>1) | 0x8000000000000000ULL) >= m
+ // if m>=b in this iteration, then in last iteration m also >= b.
+ // This can't happen
+ Is_True(m < b, ("m bigger than b and m is overflow in last
iteration\n"));
m -= b;
q |= 1;
+ m_overflow = FALSE;
}
+ else if(m >= b) {
+ m -= b;
+ q |= 1;
+ }
+ // After subtraction, m must be smaller than b. And m's 64 bit MSB must be
zero.
+ // if m's 64bit MSB is 1, then subtraction not happen in this iteration.
+ // it means b>m, then b's 64 bit MSB is also 1.
+ // Mark m overflow and in next iteration, actually m is bigger than b.
+ // Need do subtraction in next itration.
+ if (m & 0x8000000000000000ULL) {
+ Is_True(b & 0x8000000000000000ULL, ("b's 64th bit must be 1\n"));
+ m_overflow = TRUE;
+ }
m = (m<<1) | 1;
}
return 1+q;
------------------------------------------------------------------------------
BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA
The must-attend event for mobile developers. Connect with experts.
Get tools for creating Super Apps. See the latest technologies.
Sessions, hands-on labs, demos & much more. Register early & save!
http://p.sf.net/sfu/rim-blackberry-1
_______________________________________________
Open64-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/open64-devel
