Hi all,
Can gatekeeper help review this fix?
test 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.
patch:
Index: osprey/be/lno/x8664/lnotarget.cxx
===================================================================
--- osprey/be/lno/x8664/lnotarget.cxx (revision 3698)
+++ osprey/be/lno/x8664/lnotarget.cxx (working copy)
@@ -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;
Index: osprey/be/cg/x8664/exp_divrem.cxx
===================================================================
--- osprey/be/cg/x8664/exp_divrem.cxx (revision 3698)
+++ osprey/be/cg/x8664/exp_divrem.cxx (working copy)
@@ -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;
Index: osprey/be/cg/ia64/exp_divrem.cxx
===================================================================
--- osprey/be/cg/ia64/exp_divrem.cxx (revision 3698)
+++ osprey/be/cg/ia64/exp_divrem.cxx (working copy)
@@ -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;
Thanks
zhuqing
------------------------------------------------------------------------------
Got Input? Slashdot Needs You.
Take our quick survey online. Come on, we don't ask for help often.
Plus, you'll get a chance to win $100 to spend on ThinkGeek.
http://p.sf.net/sfu/slashdot-survey
_______________________________________________
Open64-devel mailing list
Open64-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open64-devel
