On Sat, 8 Dec 2007, Julian Seward wrote:
they treat
the words as signed, do a subtraction, the result is treated as signed,
and the result is checked for < 0 or > 0.
If the subtraction overflows then it is incorrect to compare the "result"
(while forgetting about the Carry) to 0.
Hmm, yes. Wasn't there a giant storm in a teacup on the gcc list a while
back about whether gcc should optimise on the basis that overflow of signed
arithmetic is undefined?
I don't understand why the carry bit is important...
But here's a patch that should fix the problem. It uses a slower but safer
and easier-to-understand method to compute the result.
Tom, can you apply and see if it fixes the problem? If so, I guess it
should be committed for 3.3.0.
Nick
Index: include/pub_tool_oset.h
===================================================================
--- include/pub_tool_oset.h (revision 7273)
+++ include/pub_tool_oset.h (working copy)
@@ -72,7 +72,7 @@
typedef struct _OSet OSet;
-// - Cmp: returns -1, 0 or 1 if key is <=, == or >= elem.
+// - Cmp: returns -1, 0 or 1 if key is <, == or > elem.
// - Alloc: allocates a chunk of memory.
// - Free: frees a chunk of memory allocated with Alloc.
Index: coregrind/m_oset.c
===================================================================
--- coregrind/m_oset.c (revision 7273)
+++ coregrind/m_oset.c (working copy)
@@ -175,7 +175,15 @@
// Compare the first word of each element. Inlining is *crucial*.
static inline Word fast_cmp(void* k, AvlNode* n)
{
- return ( *(Word*)k - *(Word*)elem_of_node(n) );
+ Word w1 = *(Word*)k;
+ Word w2 = *(Word*)elem_of_node(n);
+ // In previous versions, we tried to do this faster by doing
+ // "return w1 - w2". But it didn't always work, due to the carry bit
+ // when the subtraction overflowed(?) The branching version is slightly
+ // slows, but safer and easier to understand.
+ if (w1 > w2) return 1;
+ if (w1 < w2) return -1;
+ return 0;
}
// Compare a key and an element. Inlining is *crucial*.
@@ -490,22 +498,23 @@
while (True) {
if (curr == NULL) return NULL;
cmpres = slow_cmp(t, k, curr);
- if (cmpres < 0) curr = curr->left; else
- if (cmpres > 0) curr = curr->right; else
- return curr;
+ if (cmpres < 0) curr = curr->left;
+ else if (cmpres > 0) curr = curr->right;
+ else return curr;
}
} else {
// Fast-track special case. We use the no-check version of
// elem_of_node because it saves about 10% on lookup time. This
// shouldn't be very dangerous because each node will have been
// checked on insertion.
- Word kk = *(Word*)k;
+ Word w1 = *(Word*)k;
+ Word w2;
while (True) {
if (curr == NULL) return NULL;
- cmpres = kk - *(Word*)elem_of_node_no_check(curr);
- if (cmpres < 0) curr = curr->left; else
- if (cmpres > 0) curr = curr->right; else
- return curr;
+ w2 = *(Word*)elem_of_node_no_check(curr);
+ if (w1 < w2) curr = curr->left;
+ else if (w1 > w2) curr = curr->right;
+ else return curr;
}
}
}
-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/valgrind-developers
