[Issue 10310] New: VRP for bitwise &|^ does not always produce the tightest bound.

d-bugmail at puremagic.com d-bugmail at puremagic.com
Sat Jun 8 16:28:50 PDT 2013


http://d.puremagic.com/issues/show_bug.cgi?id=10310

           Summary: VRP for bitwise &|^ does not always produce the
                    tightest bound.
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody at puremagic.com
        ReportedBy: timon.gehr at gmx.ch


--- Comment #0 from timon.gehr at gmx.ch 2013-06-08 16:28:49 PDT ---
In DMD, VRP for bitwise &|^ does not always produce the tightest bounds.
For my own D frontend implementation, I have devised simple greedy algorithms
that do (disclaimer: proof of tightness for XOR case not carried out yet). This
is the relevant part of the source:


// (C) 2012 Timon Gehr. Feel free to redistribute (derivative works) under
artistic/gpl dual licencing. (The same as DMD.)

// T - unsigned integral type of 8*T.sizeof bytes.
// R - Pair T min, max: Range of Ts [min..max] (min and max inclusive).
// ~R - VRP for bitwise not.
// R&R - Make new R from (minAnd(.,.),maxAnd(.,.))


T maxOr(R lhs, R rhs){
    T x=0;
    auto xor=lhs.max^rhs.max;
    auto and=lhs.max&rhs.max;
     for(T d=1LU<<(8*T.sizeof-1);d;d>>=1){
        if(xor & d){
            x |= d;
            if(lhs.max&d){if(~lhs.min&d) lhs.min=0;}
            else{if(~rhs.min&d) rhs.min=0;}
        }else if(lhs.min&rhs.min&d){
            x |= d;
        }else if(and & d){
            x |= (d<<1)-1;
            break;
        }
    }
    return x;
}

T minOr(R lhs, R rhs){return ~maxAnd(~lhs,~rhs);}

T maxAnd(R lhs, R rhs){
    T x=0;
    for(T d=1LU<<(8*T.sizeof-1);d;d>>=1){
        if(lhs.max&rhs.max&d){
            x |= d;
            if(~lhs.min&d) lhs.min=0;
            if(~rhs.min&d) rhs.min=0;
        }else if(~lhs.min & d && lhs.max & d){
            lhs.max |= d-1;
        }else if(~rhs.min & d && rhs.max & d){
            rhs.max |= d-1;
        }
    }
    return x;
}

T minAnd(R lhs, R rhs){return ~maxOr(~lhs,~rhs);}

T maxXor(R lhs, R rhs){return maxOr(lhs&~rhs,~lhs&rhs);}
T minXor(R lhs, R rhs){return minOr(lhs&~rhs,~lhs&rhs);}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------


More information about the Digitalmars-d-bugs mailing list