Looks fine to me.
2011/7/29 朱庆 <zqing1...@gmail.com>
> 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
>
--
Regards,
Lai Jian-Xin
------------------------------------------------------------------------------
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
Open64-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open64-devel
