[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