Home | History | Annotate | Download | only in helgrind
      1 
      2 /*--------------------------------------------------------------------*/
      3 /*--- Sets of words, with unique set identifiers.                  ---*/
      4 /*---                                                 hg_wordset.c ---*/
      5 /*--------------------------------------------------------------------*/
      6 
      7 /*
      8    This file is part of Helgrind, a Valgrind tool for detecting errors
      9    in threaded programs.
     10 
     11    Copyright (C) 2007-2012 OpenWorks LLP
     12        info (at) open-works.co.uk
     13 
     14    This program is free software; you can redistribute it and/or
     15    modify it under the terms of the GNU General Public License as
     16    published by the Free Software Foundation; either version 2 of the
     17    License, or (at your option) any later version.
     18 
     19    This program is distributed in the hope that it will be useful, but
     20    WITHOUT ANY WARRANTY; without even the implied warranty of
     21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     22    General Public License for more details.
     23 
     24    You should have received a copy of the GNU General Public License
     25    along with this program; if not, write to the Free Software
     26    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
     27    02111-1307, USA.
     28 
     29    The GNU General Public License is contained in the file COPYING.
     30 
     31    Neither the names of the U.S. Department of Energy nor the
     32    University of California nor the names of its contributors may be
     33    used to endorse or promote products derived from this software
     34    without prior written permission.
     35 */
     36 
     37 #include "pub_tool_basics.h"
     38 #include "pub_tool_libcassert.h"
     39 #include "pub_tool_libcbase.h"
     40 #include "pub_tool_libcprint.h"
     41 #include "pub_tool_threadstate.h"
     42 #include "pub_tool_wordfm.h"
     43 
     44 #include "hg_basics.h"
     45 #include "hg_wordset.h"     /* self */
     46 
     47 // define to 1 to have (a lot of) debugging of add/re-use/die WSU entries.
     48 #define HG_DEBUG 0
     49 
     50 //------------------------------------------------------------------//
     51 //--- Word Cache                                                 ---//
     52 //------------------------------------------------------------------//
     53 
     54 typedef
     55    struct { UWord arg1; UWord arg2; UWord res; }
     56    WCacheEnt;
     57 
     58 /* Each cache is a fixed sized array of N_WCACHE_STAT_MAX entries.
     59    However only the first .dynMax are used.  This is because at some
     60    point, expanding the cache further overall gives a slowdown because
     61    searching more entries more than negates any performance advantage
     62    from caching those entries in the first place.  Hence use .dynMax
     63    to allow the size of the cache(s) to be set differently for each
     64    different WordSetU. */
     65 #define N_WCACHE_STAT_MAX 32
     66 typedef
     67    struct {
     68       WCacheEnt ent[N_WCACHE_STAT_MAX];
     69       UWord     dynMax; /* 1 .. N_WCACHE_STAT_MAX inclusive */
     70       UWord     inUse;  /* 0 .. dynMax inclusive */
     71    }
     72    WCache;
     73 
     74 #define WCache_INIT(_zzcache,_zzdynmax)                              \
     75    do {                                                              \
     76       tl_assert((_zzdynmax) >= 1);                                   \
     77       tl_assert((_zzdynmax) <= N_WCACHE_STAT_MAX);                   \
     78       (_zzcache).dynMax = (_zzdynmax);                               \
     79       (_zzcache).inUse = 0;                                          \
     80    } while (0)
     81 
     82 #define WCache_LOOKUP_AND_RETURN(_retty,_zzcache,_zzarg1,_zzarg2)    \
     83    do {                                                              \
     84       UWord   _i;                                                    \
     85       UWord   _arg1  = (UWord)(_zzarg1);                             \
     86       UWord   _arg2  = (UWord)(_zzarg2);                             \
     87       WCache* _cache = &(_zzcache);                                  \
     88       tl_assert(_cache->dynMax >= 1);                                \
     89       tl_assert(_cache->dynMax <= N_WCACHE_STAT_MAX);                \
     90       tl_assert(_cache->inUse >= 0);                                 \
     91       tl_assert(_cache->inUse <= _cache->dynMax);                    \
     92       if (_cache->inUse > 0) {                                       \
     93          if (_cache->ent[0].arg1 == _arg1                            \
     94              && _cache->ent[0].arg2 == _arg2)                        \
     95             return (_retty)_cache->ent[0].res;                       \
     96          for (_i = 1; _i < _cache->inUse; _i++) {                    \
     97             if (_cache->ent[_i].arg1 == _arg1                        \
     98                 && _cache->ent[_i].arg2 == _arg2) {                  \
     99                WCacheEnt tmp     = _cache->ent[_i-1];                \
    100                _cache->ent[_i-1] = _cache->ent[_i];                  \
    101                _cache->ent[_i]   = tmp;                              \
    102                return (_retty)_cache->ent[_i-1].res;                 \
    103             }                                                        \
    104          }                                                           \
    105       }                                                              \
    106    } while (0)
    107 
    108 #define WCache_UPDATE(_zzcache,_zzarg1,_zzarg2,_zzresult)            \
    109    do {                                                              \
    110       Word    _i;                                                    \
    111       UWord   _arg1  = (UWord)(_zzarg1);                             \
    112       UWord   _arg2  = (UWord)(_zzarg2);                             \
    113       UWord   _res   = (UWord)(_zzresult);                           \
    114       WCache* _cache = &(_zzcache);                                  \
    115       tl_assert(_cache->dynMax >= 1);                                \
    116       tl_assert(_cache->dynMax <= N_WCACHE_STAT_MAX);                \
    117       tl_assert(_cache->inUse >= 0);                                 \
    118       tl_assert(_cache->inUse <= _cache->dynMax);                    \
    119       if (_cache->inUse < _cache->dynMax)                            \
    120          _cache->inUse++;                                            \
    121       for (_i = _cache->inUse-1; _i >= 1; _i--)                      \
    122          _cache->ent[_i] = _cache->ent[_i-1];                        \
    123       _cache->ent[0].arg1 = _arg1;                                   \
    124       _cache->ent[0].arg2 = _arg2;                                   \
    125       _cache->ent[0].res  = _res;                                    \
    126    } while (0)
    127 
    128 
    129 //------------------------------------------------------------------//
    130 //---                          WordSet                           ---//
    131 //---                       Implementation                       ---//
    132 //------------------------------------------------------------------//
    133 
    134 typedef
    135    struct {
    136       WordSetU* owner; /* for sanity checking */
    137       UWord*    words;
    138       UWord     size; /* Really this should be SizeT */
    139    }
    140    WordVec;
    141 
    142 /* ix2vec[0 .. ix2vec_used-1] are pointers to the lock sets (WordVecs)
    143    really.  vec2ix is the inverse mapping, mapping WordVec* to the
    144    corresponding ix2vec entry number.  The two mappings are mutually
    145    redundant.
    146 
    147    If a WordVec WV is marked as dead by HG(dieWS), WV is removed from
    148    vec2ix. The entry of the dead WVs in ix2vec are used to maintain a
    149    linked list of free (to be re-used) ix2vec entries. */
    150 struct _WordSetU {
    151       void*     (*alloc)(HChar*,SizeT);
    152       HChar*    cc;
    153       void      (*dealloc)(void*);
    154       WordFM*   vec2ix; /* WordVec-to-WordSet mapping tree */
    155       WordVec** ix2vec; /* WordSet-to-WordVec mapping array */
    156       UWord     ix2vec_size;
    157       UWord     ix2vec_used;
    158       WordVec** ix2vec_free;
    159       WordSet   empty; /* cached, for speed */
    160       /* Caches for some operations */
    161       WCache    cache_addTo;
    162       WCache    cache_delFrom;
    163       WCache    cache_intersect;
    164       WCache    cache_minus;
    165       /* Stats */
    166       UWord     n_add;
    167       UWord     n_add_uncached;
    168       UWord     n_del;
    169       UWord     n_del_uncached;
    170       UWord     n_die;
    171       UWord     n_union;
    172       UWord     n_intersect;
    173       UWord     n_intersect_uncached;
    174       UWord     n_minus;
    175       UWord     n_minus_uncached;
    176       UWord     n_elem;
    177       UWord     n_doubleton;
    178       UWord     n_isEmpty;
    179       UWord     n_isSingleton;
    180       UWord     n_anyElementOf;
    181       UWord     n_isSubsetOf;
    182    };
    183 
    184 /* Create a new WordVec of the given size. */
    185 
    186 static WordVec* new_WV_of_size ( WordSetU* wsu, UWord sz )
    187 {
    188    WordVec* wv;
    189    tl_assert(sz >= 0);
    190    wv = wsu->alloc( wsu->cc, sizeof(WordVec) );
    191    wv->owner = wsu;
    192    wv->words = NULL;
    193    wv->size = sz;
    194    if (sz > 0) {
    195      wv->words = wsu->alloc( wsu->cc, (SizeT)sz * sizeof(UWord) );
    196    }
    197    return wv;
    198 }
    199 
    200 static void delete_WV ( WordVec* wv )
    201 {
    202    void (*dealloc)(void*) = wv->owner->dealloc;
    203    if (wv->words) {
    204       dealloc(wv->words);
    205    }
    206    dealloc(wv);
    207 }
    208 static void delete_WV_for_FM ( UWord wv ) {
    209    delete_WV( (WordVec*)wv );
    210 }
    211 
    212 static Word cmp_WordVecs_for_FM ( UWord wv1W, UWord wv2W )
    213 {
    214    UWord    i;
    215    WordVec* wv1    = (WordVec*)wv1W;
    216    WordVec* wv2    = (WordVec*)wv2W;
    217 
    218    // WordVecs with smaller size are smaller.
    219    if (wv1->size < wv2->size) {
    220       return -1;
    221    }
    222    if (wv1->size > wv2->size) {
    223       return 1;
    224    }
    225 
    226    // Sizes are equal => order based on content.
    227    for (i = 0; i < wv1->size; i++) {
    228       if (wv1->words[i] == wv2->words[i])
    229          continue;
    230       if (wv1->words[i] < wv2->words[i])
    231          return -1;
    232       if (wv1->words[i] > wv2->words[i])
    233          return 1;
    234       tl_assert(0);
    235    }
    236    return 0; /* identical */
    237 }
    238 
    239 static void ensure_ix2vec_space ( WordSetU* wsu )
    240 {
    241    UInt      i, new_sz;
    242    WordVec** new_vec;
    243    tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size);
    244    if (wsu->ix2vec_used < wsu->ix2vec_size)
    245       return;
    246    new_sz = 2 * wsu->ix2vec_size;
    247    if (new_sz == 0) new_sz = 1;
    248    new_vec = wsu->alloc( wsu->cc, new_sz * sizeof(WordVec*) );
    249    tl_assert(new_vec);
    250    for (i = 0; i < wsu->ix2vec_size; i++)
    251       new_vec[i] = wsu->ix2vec[i];
    252    if (wsu->ix2vec)
    253       wsu->dealloc(wsu->ix2vec);
    254    wsu->ix2vec = new_vec;
    255    wsu->ix2vec_size = new_sz;
    256 }
    257 
    258 /* True if wv is a dead entry (i.e. is in the linked list of free to be re-used
    259    entries in ix2vec). */
    260 static inline Bool is_dead ( WordSetU* wsu, WordVec* wv )
    261 {
    262    if (wv == NULL) /* last element in free linked list in ix2vec */
    263       return True;
    264    else
    265       return (WordVec**)wv >= &(wsu->ix2vec[1])
    266          &&  (WordVec**)wv < &(wsu->ix2vec[wsu->ix2vec_size]);
    267 }
    268 /* Index into a WordSetU, doing the obvious range check.  Failure of
    269    the assertions marked XXX and YYY is an indication of passing the
    270    wrong WordSetU* in the public API of this module.
    271    Accessing a dead ws will assert. */
    272 static WordVec* do_ix2vec ( WordSetU* wsu, WordSet ws )
    273 {
    274    WordVec* wv;
    275    tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size);
    276    if (wsu->ix2vec_used > 0)
    277       tl_assert(wsu->ix2vec);
    278    /* If this assertion fails, it may mean you supplied a 'ws'
    279       that does not come from the 'wsu' universe. */
    280    tl_assert(ws < wsu->ix2vec_used); /* XXX */
    281    wv = wsu->ix2vec[ws];
    282    /* Make absolutely sure that 'ws' is a non dead member of 'wsu'. */
    283    tl_assert(wv);
    284    tl_assert(!is_dead(wsu,wv));
    285    tl_assert(wv->owner == wsu); /* YYY */
    286    return wv;
    287 }
    288 
    289 /* Same as do_ix2vec but returns NULL for a dead ws. */
    290 static WordVec* do_ix2vec_with_dead ( WordSetU* wsu, WordSet ws )
    291 {
    292    WordVec* wv;
    293    tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size);
    294    if (wsu->ix2vec_used > 0)
    295       tl_assert(wsu->ix2vec);
    296    /* If this assertion fails, it may mean you supplied a 'ws'
    297       that does not come from the 'wsu' universe. */
    298    tl_assert(ws < wsu->ix2vec_used); /* XXX */
    299    wv = wsu->ix2vec[ws];
    300    /* Make absolutely sure that 'ws' is either dead or a member of 'wsu'. */
    301    if (is_dead(wsu,wv))
    302       wv = NULL;
    303    else
    304       tl_assert(wv->owner == wsu); /* YYY */
    305    return wv;
    306 }
    307 
    308 /* See if wv is contained within wsu.  If so, deallocate wv and return
    309    the index of the already-present copy.  If not, add wv to both the
    310    vec2ix and ix2vec mappings and return its index.
    311 */
    312 static WordSet add_or_dealloc_WordVec( WordSetU* wsu, WordVec* wv_new )
    313 {
    314    Bool     have;
    315    WordVec* wv_old;
    316    UWord/*Set*/ ix_old = -1;
    317    /* Really WordSet, but need something that can safely be casted to
    318       a Word* in the lookupFM.  Making it WordSet (which is 32 bits)
    319       causes failures on a 64-bit platform. */
    320    tl_assert(wv_new->owner == wsu);
    321    have = VG_(lookupFM)( wsu->vec2ix,
    322                          (Word*)&wv_old, (Word*)&ix_old,
    323                          (Word)wv_new );
    324    if (have) {
    325       tl_assert(wv_old != wv_new);
    326       tl_assert(wv_old);
    327       tl_assert(wv_old->owner == wsu);
    328       tl_assert(ix_old < wsu->ix2vec_used);
    329       tl_assert(wsu->ix2vec[ix_old] == wv_old);
    330       delete_WV( wv_new );
    331       return (WordSet)ix_old;
    332    } else if (wsu->ix2vec_free) {
    333       WordSet ws;
    334       tl_assert(is_dead(wsu,(WordVec*)wsu->ix2vec_free));
    335       ws = wsu->ix2vec_free - &(wsu->ix2vec[0]);
    336       tl_assert(wsu->ix2vec[ws] == NULL || is_dead(wsu,wsu->ix2vec[ws]));
    337       wsu->ix2vec_free = (WordVec **) wsu->ix2vec[ws];
    338       wsu->ix2vec[ws] = wv_new;
    339       VG_(addToFM)( wsu->vec2ix, (Word)wv_new, ws );
    340       if (HG_DEBUG) VG_(printf)("aodW %s re-use free %d %p\n", wsu->cc, (Int)ws, wv_new );
    341       return ws;
    342    } else {
    343       ensure_ix2vec_space( wsu );
    344       tl_assert(wsu->ix2vec);
    345       tl_assert(wsu->ix2vec_used < wsu->ix2vec_size);
    346       wsu->ix2vec[wsu->ix2vec_used] = wv_new;
    347       VG_(addToFM)( wsu->vec2ix, (Word)wv_new, (Word)wsu->ix2vec_used );
    348       if (HG_DEBUG) VG_(printf)("aodW %s %d %p\n", wsu->cc, (Int)wsu->ix2vec_used, wv_new  );
    349       wsu->ix2vec_used++;
    350       tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size);
    351       return (WordSet)(wsu->ix2vec_used - 1);
    352    }
    353 }
    354 
    355 
    356 WordSetU* HG_(newWordSetU) ( void* (*alloc_nofail)( HChar*, SizeT ),
    357                              HChar* cc,
    358                              void  (*dealloc)(void*),
    359                              Word  cacheSize )
    360 {
    361    WordSetU* wsu;
    362    WordVec*  empty;
    363 
    364    wsu          = alloc_nofail( cc, sizeof(WordSetU) );
    365    VG_(memset)( wsu, 0, sizeof(WordSetU) );
    366    wsu->alloc   = alloc_nofail;
    367    wsu->cc      = cc;
    368    wsu->dealloc = dealloc;
    369    wsu->vec2ix  = VG_(newFM)( alloc_nofail, cc,
    370                               dealloc, cmp_WordVecs_for_FM );
    371    wsu->ix2vec_used = 0;
    372    wsu->ix2vec_size = 0;
    373    wsu->ix2vec      = NULL;
    374    wsu->ix2vec_free = NULL;
    375    WCache_INIT(wsu->cache_addTo,     cacheSize);
    376    WCache_INIT(wsu->cache_delFrom,   cacheSize);
    377    WCache_INIT(wsu->cache_intersect, cacheSize);
    378    WCache_INIT(wsu->cache_minus,     cacheSize);
    379    empty = new_WV_of_size( wsu, 0 );
    380    wsu->empty = add_or_dealloc_WordVec( wsu, empty );
    381 
    382    return wsu;
    383 }
    384 
    385 void HG_(deleteWordSetU) ( WordSetU* wsu )
    386 {
    387    void (*dealloc)(void*) = wsu->dealloc;
    388    tl_assert(wsu->vec2ix);
    389    VG_(deleteFM)( wsu->vec2ix, delete_WV_for_FM, NULL/*val-finalizer*/ );
    390    if (wsu->ix2vec)
    391       dealloc(wsu->ix2vec);
    392    dealloc(wsu);
    393 }
    394 
    395 WordSet HG_(emptyWS) ( WordSetU* wsu )
    396 {
    397    return wsu->empty;
    398 }
    399 
    400 Bool HG_(isEmptyWS) ( WordSetU* wsu, WordSet ws )
    401 {
    402    WordVec* wv = do_ix2vec( wsu, ws );
    403    wsu->n_isEmpty++;
    404    if (wv->size == 0) {
    405       tl_assert(ws == wsu->empty);
    406       return True;
    407    } else {
    408       tl_assert(ws != wsu->empty);
    409       return False;
    410    }
    411 }
    412 
    413 Bool HG_(isSingletonWS) ( WordSetU* wsu, WordSet ws, UWord w )
    414 {
    415    WordVec* wv;
    416    tl_assert(wsu);
    417    wsu->n_isSingleton++;
    418    wv = do_ix2vec( wsu, ws );
    419    return (Bool)(wv->size == 1 && wv->words[0] == w);
    420 }
    421 
    422 UWord HG_(cardinalityWS) ( WordSetU* wsu, WordSet ws )
    423 {
    424    WordVec* wv;
    425    tl_assert(wsu);
    426    wv = do_ix2vec( wsu, ws );
    427    tl_assert(wv->size >= 0);
    428    return wv->size;
    429 }
    430 
    431 UWord HG_(anyElementOfWS) ( WordSetU* wsu, WordSet ws )
    432 {
    433    WordVec* wv;
    434    tl_assert(wsu);
    435    wsu->n_anyElementOf++;
    436    wv = do_ix2vec( wsu, ws );
    437    tl_assert(wv->size >= 1);
    438    return wv->words[0];
    439 }
    440 
    441 UWord HG_(cardinalityWSU) ( WordSetU* wsu )
    442 {
    443    tl_assert(wsu);
    444    return wsu->ix2vec_used;
    445 }
    446 
    447 void HG_(getPayloadWS) ( /*OUT*/UWord** words, /*OUT*/UWord* nWords,
    448                          WordSetU* wsu, WordSet ws )
    449 {
    450    WordVec* wv;
    451    if (HG_DEBUG) VG_(printf)("getPayloadWS %s %d\n", wsu->cc, (Int)ws);
    452    tl_assert(wsu);
    453    wv = do_ix2vec( wsu, ws );
    454    tl_assert(wv->size >= 0);
    455    *nWords = wv->size;
    456    *words  = wv->words;
    457 }
    458 
    459 void HG_(dieWS) ( WordSetU* wsu, WordSet ws )
    460 {
    461    WordVec* wv = do_ix2vec_with_dead( wsu, ws );
    462    WordVec* wv_in_vec2ix;
    463    UWord/*Set*/ wv_ix = -1;
    464 
    465    if (HG_DEBUG) VG_(printf)("dieWS %s %d %p\n", wsu->cc, (Int)ws, wv);
    466 
    467    if (ws == 0)
    468       return; // we never die the empty set.
    469 
    470    if (!wv)
    471       return; // already dead. (or a bug ?).
    472 
    473    wsu->n_die++;
    474 
    475 
    476    wsu->ix2vec[ws] = (WordVec*) wsu->ix2vec_free;
    477    wsu->ix2vec_free = &wsu->ix2vec[ws];
    478 
    479    VG_(delFromFM) ( wsu->vec2ix,
    480                     (Word*)&wv_in_vec2ix, (Word*)&wv_ix,
    481                     (Word)wv );
    482 
    483    if (HG_DEBUG) VG_(printf)("dieWS wv_ix %d\n", (Int)wv_ix);
    484    tl_assert (wv_ix);
    485    tl_assert (wv_ix == ws);
    486 
    487    delete_WV( wv );
    488 
    489    wsu->cache_addTo.inUse = 0;
    490    wsu->cache_delFrom.inUse = 0;
    491    wsu->cache_intersect.inUse = 0;
    492    wsu->cache_minus.inUse = 0;
    493 }
    494 
    495 Bool HG_(plausibleWS) ( WordSetU* wsu, WordSet ws )
    496 {
    497    if (wsu == NULL) return False;
    498    if (ws < 0 || ws >= wsu->ix2vec_used)
    499       return False;
    500    return True;
    501 }
    502 
    503 Bool HG_(saneWS_SLOW) ( WordSetU* wsu, WordSet ws )
    504 {
    505    WordVec* wv;
    506    UWord    i;
    507    if (wsu == NULL) return False;
    508    if (ws < 0 || ws >= wsu->ix2vec_used)
    509       return False;
    510    wv = do_ix2vec( wsu, ws );
    511    /* can never happen .. do_ix2vec will assert instead.  Oh well. */
    512    if (wv->owner != wsu) return False;
    513    if (wv->size < 0) return False;
    514    if (wv->size > 0) {
    515       for (i = 0; i < wv->size-1; i++) {
    516          if (wv->words[i] >= wv->words[i+1])
    517             return False;
    518       }
    519    }
    520    return True;
    521 }
    522 
    523 Bool HG_(elemWS) ( WordSetU* wsu, WordSet ws, UWord w )
    524 {
    525    UWord    i;
    526    WordVec* wv = do_ix2vec( wsu, ws );
    527    wsu->n_elem++;
    528    for (i = 0; i < wv->size; i++) {
    529       if (wv->words[i] == w)
    530          return True;
    531    }
    532    return False;
    533 }
    534 
    535 WordSet HG_(doubletonWS) ( WordSetU* wsu, UWord w1, UWord w2 )
    536 {
    537    WordVec* wv;
    538    wsu->n_doubleton++;
    539    if (w1 == w2) {
    540       wv = new_WV_of_size(wsu, 1);
    541       wv->words[0] = w1;
    542    }
    543    else if (w1 < w2) {
    544       wv = new_WV_of_size(wsu, 2);
    545       wv->words[0] = w1;
    546       wv->words[1] = w2;
    547    }
    548    else {
    549       tl_assert(w1 > w2);
    550       wv = new_WV_of_size(wsu, 2);
    551       wv->words[0] = w2;
    552       wv->words[1] = w1;
    553    }
    554    return add_or_dealloc_WordVec( wsu, wv );
    555 }
    556 
    557 WordSet HG_(singletonWS) ( WordSetU* wsu, UWord w )
    558 {
    559    return HG_(doubletonWS)( wsu, w, w );
    560 }
    561 
    562 WordSet HG_(isSubsetOf) ( WordSetU* wsu, WordSet small, WordSet big )
    563 {
    564    wsu->n_isSubsetOf++;
    565    return small == HG_(intersectWS)( wsu, small, big );
    566 }
    567 
    568 void HG_(ppWS) ( WordSetU* wsu, WordSet ws )
    569 {
    570    UWord    i;
    571    WordVec* wv;
    572    tl_assert(wsu);
    573    wv = do_ix2vec( wsu, ws );
    574    VG_(printf)("{");
    575    for (i = 0; i < wv->size; i++) {
    576       VG_(printf)("%p", (void*)wv->words[i]);
    577       if (i < wv->size-1)
    578          VG_(printf)(",");
    579    }
    580    VG_(printf)("}");
    581 }
    582 
    583 void HG_(ppWSUstats) ( WordSetU* wsu, HChar* name )
    584 {
    585    VG_(printf)("   WordSet \"%s\":\n", name);
    586    VG_(printf)("      addTo        %10lu (%lu uncached)\n",
    587                wsu->n_add, wsu->n_add_uncached);
    588    VG_(printf)("      delFrom      %10lu (%lu uncached)\n",
    589                wsu->n_del, wsu->n_del_uncached);
    590    VG_(printf)("      union        %10lu\n", wsu->n_union);
    591    VG_(printf)("      intersect    %10lu (%lu uncached) "
    592                "[nb. incl isSubsetOf]\n",
    593                wsu->n_intersect, wsu->n_intersect_uncached);
    594    VG_(printf)("      minus        %10lu (%lu uncached)\n",
    595                wsu->n_minus, wsu->n_minus_uncached);
    596    VG_(printf)("      elem         %10lu\n",   wsu->n_elem);
    597    VG_(printf)("      doubleton    %10lu\n",   wsu->n_doubleton);
    598    VG_(printf)("      isEmpty      %10lu\n",   wsu->n_isEmpty);
    599    VG_(printf)("      isSingleton  %10lu\n",   wsu->n_isSingleton);
    600    VG_(printf)("      anyElementOf %10lu\n",   wsu->n_anyElementOf);
    601    VG_(printf)("      isSubsetOf   %10lu\n",   wsu->n_isSubsetOf);
    602    VG_(printf)("      dieWS        %10lu\n",   wsu->n_die);
    603 }
    604 
    605 WordSet HG_(addToWS) ( WordSetU* wsu, WordSet ws, UWord w )
    606 {
    607    UWord    k, j;
    608    WordVec* wv_new;
    609    WordVec* wv;
    610    WordSet  result = (WordSet)(-1); /* bogus */
    611 
    612    wsu->n_add++;
    613    WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_addTo, ws, w);
    614    wsu->n_add_uncached++;
    615 
    616    /* If already present, this is a no-op. */
    617    wv = do_ix2vec( wsu, ws );
    618    for (k = 0; k < wv->size; k++) {
    619       if (wv->words[k] == w) {
    620          result = ws;
    621          goto out;
    622       }
    623    }
    624    /* Ok, not present.  Build a new one ... */
    625    wv_new = new_WV_of_size( wsu, wv->size + 1 );
    626    k = j = 0;
    627    for (; k < wv->size && wv->words[k] < w; k++) {
    628       wv_new->words[j++] = wv->words[k];
    629    }
    630    wv_new->words[j++] = w;
    631    for (; k < wv->size; k++) {
    632       tl_assert(wv->words[k] > w);
    633       wv_new->words[j++] = wv->words[k];
    634    }
    635    tl_assert(j == wv_new->size);
    636 
    637    /* Find any existing copy, or add the new one. */
    638    result = add_or_dealloc_WordVec( wsu, wv_new );
    639    tl_assert(result != (WordSet)(-1));
    640 
    641   out:
    642    WCache_UPDATE(wsu->cache_addTo, ws, w, result);
    643    return result;
    644 }
    645 
    646 WordSet HG_(delFromWS) ( WordSetU* wsu, WordSet ws, UWord w )
    647 {
    648    UWord    i, j, k;
    649    WordVec* wv_new;
    650    WordSet  result = (WordSet)(-1); /* bogus */
    651    WordVec* wv = do_ix2vec( wsu, ws );
    652 
    653    wsu->n_del++;
    654 
    655    /* special case empty set */
    656    if (wv->size == 0) {
    657       tl_assert(ws == wsu->empty);
    658       return ws;
    659    }
    660 
    661    WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_delFrom, ws, w);
    662    wsu->n_del_uncached++;
    663 
    664    /* If not already present, this is a no-op. */
    665    for (i = 0; i < wv->size; i++) {
    666       if (wv->words[i] == w)
    667          break;
    668    }
    669    if (i == wv->size) {
    670       result = ws;
    671       goto out;
    672    }
    673    /* So w is present in ws, and the new set will be one element
    674       smaller. */
    675    tl_assert(i >= 0 && i < wv->size);
    676    tl_assert(wv->size > 0);
    677 
    678    wv_new = new_WV_of_size( wsu, wv->size - 1 );
    679    j = k = 0;
    680    for (; j < wv->size; j++) {
    681       if (j == i)
    682          continue;
    683       wv_new->words[k++] = wv->words[j];
    684    }
    685    tl_assert(k == wv_new->size);
    686 
    687    result = add_or_dealloc_WordVec( wsu, wv_new );
    688    if (wv->size == 1) {
    689       tl_assert(result == wsu->empty);
    690    }
    691 
    692   out:
    693    WCache_UPDATE(wsu->cache_delFrom, ws, w, result);
    694    return result;
    695 }
    696 
    697 WordSet HG_(unionWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
    698 {
    699    UWord    i1, i2, k, sz;
    700    WordVec* wv_new;
    701    WordVec* wv1 = do_ix2vec( wsu, ws1 );
    702    WordVec* wv2 = do_ix2vec( wsu, ws2 );
    703    wsu->n_union++;
    704    sz = 0;
    705    i1 = i2 = 0;
    706    while (1) {
    707       if (i1 >= wv1->size || i2 >= wv2->size)
    708          break;
    709       sz++;
    710       if (wv1->words[i1] < wv2->words[i2]) {
    711          i1++;
    712       } else
    713       if (wv1->words[i1] > wv2->words[i2]) {
    714          i2++;
    715       } else {
    716          i1++;
    717          i2++;
    718       }
    719    }
    720    tl_assert(i1 <= wv1->size);
    721    tl_assert(i2 <= wv2->size);
    722    tl_assert(i1 == wv1->size || i2 == wv2->size);
    723    if (i1 == wv1->size && i2 < wv2->size) {
    724       sz += (wv2->size - i2);
    725    }
    726    if (i2 == wv2->size && i1 < wv1->size) {
    727       sz += (wv1->size - i1);
    728    }
    729 
    730    wv_new = new_WV_of_size( wsu, sz );
    731    k = 0;
    732 
    733    i1 = i2 = 0;
    734    while (1) {
    735       if (i1 >= wv1->size || i2 >= wv2->size)
    736          break;
    737       if (wv1->words[i1] < wv2->words[i2]) {
    738          wv_new->words[k++] = wv1->words[i1];
    739          i1++;
    740       } else
    741       if (wv1->words[i1] > wv2->words[i2]) {
    742          wv_new->words[k++] = wv2->words[i2];
    743          i2++;
    744       } else {
    745          wv_new->words[k++] = wv1->words[i1];
    746          i1++;
    747          i2++;
    748       }
    749    }
    750    tl_assert(i1 <= wv1->size);
    751    tl_assert(i2 <= wv2->size);
    752    tl_assert(i1 == wv1->size || i2 == wv2->size);
    753    if (i1 == wv1->size && i2 < wv2->size) {
    754       while (i2 < wv2->size)
    755          wv_new->words[k++] = wv2->words[i2++];
    756    }
    757    if (i2 == wv2->size && i1 < wv1->size) {
    758       while (i1 < wv1->size)
    759          wv_new->words[k++] = wv1->words[i1++];
    760    }
    761 
    762    tl_assert(k == sz);
    763 
    764    return add_or_dealloc_WordVec( wsu, wv_new );
    765 }
    766 
    767 WordSet HG_(intersectWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
    768 {
    769    UWord    i1, i2, k, sz;
    770    WordSet  ws_new = (WordSet)(-1); /* bogus */
    771    WordVec* wv_new;
    772    WordVec* wv1;
    773    WordVec* wv2;
    774 
    775    wsu->n_intersect++;
    776 
    777    /* Deal with an obvious case fast. */
    778    if (ws1 == ws2)
    779       return ws1;
    780 
    781    /* Since intersect(x,y) == intersect(y,x), convert both variants to
    782       the same query.  This reduces the number of variants the cache
    783       has to deal with. */
    784    if (ws1 > ws2) {
    785       WordSet wst = ws1; ws1 = ws2; ws2 = wst;
    786    }
    787 
    788    WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_intersect, ws1, ws2);
    789    wsu->n_intersect_uncached++;
    790 
    791    wv1 = do_ix2vec( wsu, ws1 );
    792    wv2 = do_ix2vec( wsu, ws2 );
    793    sz = 0;
    794    i1 = i2 = 0;
    795    while (1) {
    796       if (i1 >= wv1->size || i2 >= wv2->size)
    797          break;
    798       if (wv1->words[i1] < wv2->words[i2]) {
    799          i1++;
    800       } else
    801       if (wv1->words[i1] > wv2->words[i2]) {
    802          i2++;
    803       } else {
    804          sz++;
    805          i1++;
    806          i2++;
    807       }
    808    }
    809    tl_assert(i1 <= wv1->size);
    810    tl_assert(i2 <= wv2->size);
    811    tl_assert(i1 == wv1->size || i2 == wv2->size);
    812 
    813    wv_new = new_WV_of_size( wsu, sz );
    814    k = 0;
    815 
    816    i1 = i2 = 0;
    817    while (1) {
    818       if (i1 >= wv1->size || i2 >= wv2->size)
    819          break;
    820       if (wv1->words[i1] < wv2->words[i2]) {
    821          i1++;
    822       } else
    823       if (wv1->words[i1] > wv2->words[i2]) {
    824          i2++;
    825       } else {
    826          wv_new->words[k++] = wv1->words[i1];
    827          i1++;
    828          i2++;
    829       }
    830    }
    831    tl_assert(i1 <= wv1->size);
    832    tl_assert(i2 <= wv2->size);
    833    tl_assert(i1 == wv1->size || i2 == wv2->size);
    834 
    835    tl_assert(k == sz);
    836 
    837    ws_new = add_or_dealloc_WordVec( wsu, wv_new );
    838    if (sz == 0) {
    839       tl_assert(ws_new == wsu->empty);
    840    }
    841 
    842    tl_assert(ws_new != (WordSet)(-1));
    843    WCache_UPDATE(wsu->cache_intersect, ws1, ws2, ws_new);
    844 
    845    return ws_new;
    846 }
    847 
    848 WordSet HG_(minusWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
    849 {
    850    UWord    i1, i2, k, sz;
    851    WordSet  ws_new = (WordSet)(-1); /* bogus */
    852    WordVec* wv_new;
    853    WordVec* wv1;
    854    WordVec* wv2;
    855 
    856    wsu->n_minus++;
    857    WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_minus, ws1, ws2);
    858    wsu->n_minus_uncached++;
    859 
    860    wv1 = do_ix2vec( wsu, ws1 );
    861    wv2 = do_ix2vec( wsu, ws2 );
    862    sz = 0;
    863    i1 = i2 = 0;
    864    while (1) {
    865       if (i1 >= wv1->size || i2 >= wv2->size)
    866          break;
    867       if (wv1->words[i1] < wv2->words[i2]) {
    868          sz++;
    869          i1++;
    870       } else
    871       if (wv1->words[i1] > wv2->words[i2]) {
    872          i2++;
    873       } else {
    874          i1++;
    875          i2++;
    876       }
    877    }
    878    tl_assert(i1 <= wv1->size);
    879    tl_assert(i2 <= wv2->size);
    880    tl_assert(i1 == wv1->size || i2 == wv2->size);
    881    if (i2 == wv2->size && i1 < wv1->size) {
    882       sz += (wv1->size - i1);
    883    }
    884 
    885    wv_new = new_WV_of_size( wsu, sz );
    886    k = 0;
    887 
    888    i1 = i2 = 0;
    889    while (1) {
    890       if (i1 >= wv1->size || i2 >= wv2->size)
    891          break;
    892       if (wv1->words[i1] < wv2->words[i2]) {
    893          wv_new->words[k++] = wv1->words[i1];
    894          i1++;
    895       } else
    896       if (wv1->words[i1] > wv2->words[i2]) {
    897          i2++;
    898       } else {
    899          i1++;
    900          i2++;
    901       }
    902    }
    903    tl_assert(i1 <= wv1->size);
    904    tl_assert(i2 <= wv2->size);
    905    tl_assert(i1 == wv1->size || i2 == wv2->size);
    906    if (i2 == wv2->size && i1 < wv1->size) {
    907       while (i1 < wv1->size)
    908          wv_new->words[k++] = wv1->words[i1++];
    909    }
    910 
    911    tl_assert(k == sz);
    912 
    913    ws_new = add_or_dealloc_WordVec( wsu, wv_new );
    914    if (sz == 0) {
    915       tl_assert(ws_new == wsu->empty);
    916    }
    917 
    918    tl_assert(ws_new != (WordSet)(-1));
    919    WCache_UPDATE(wsu->cache_minus, ws1, ws2, ws_new);
    920 
    921    return ws_new;
    922 }
    923 
    924 static __attribute__((unused))
    925 void show_WS ( WordSetU* wsu, WordSet ws )
    926 {
    927    UWord i;
    928    WordVec* wv = do_ix2vec( wsu, ws );
    929    VG_(printf)("#%u{", ws);
    930    for (i = 0; i < wv->size; i++) {
    931       VG_(printf)("%lu", wv->words[i]);
    932       if (i < wv->size-1)
    933          VG_(printf)(",");
    934    }
    935    VG_(printf)("}\n");
    936 }
    937 
    938 //------------------------------------------------------------------//
    939 //---                        end WordSet                         ---//
    940 //---                       Implementation                       ---//
    941 //------------------------------------------------------------------//
    942 
    943 /*--------------------------------------------------------------------*/
    944 /*--- end                                             hg_wordset.c ---*/
    945 /*--------------------------------------------------------------------*/
    946