1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This file is part of drd, a thread error detector. 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 4436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Copyright (C) 2006-2013 Bart Van Assche <bvanassche@acm.org>. 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is free software; you can redistribute it and/or 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown modify it under the terms of the GNU General Public License as 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown published by the Free Software Foundation; either version 2 of the 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown License, or (at your option) any later version. 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is distributed in the hope that it will be useful, but 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WITHOUT ANY WARRANTY; without even the implied warranty of 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown General Public License for more details. 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown You should have received a copy of the GNU General Public License 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown along with this program; if not, write to the Free Software 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 02111-1307, USA. 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown The GNU General Public License is contained in the file COPYING. 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "drd_basics.h" /* DRD_() */ 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "drd_bitmap.h" 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "drd_error.h" 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "drd_suppression.h" 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_drd_bitmap.h" 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_basics.h" /* Addr, SizeT */ 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_debuginfo.h" /* VG_(get_objname)() */ 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_libcassert.h" /* tl_assert() */ 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_libcbase.h" /* VG_(memset) */ 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_libcprint.h" /* VG_(printf) */ 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_machine.h" /* VG_(get_IP)() */ 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_tool_mallocfree.h" /* VG_(malloc), VG_(free) */ 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Local function declarations. */ 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void bm2_merge(struct bitmap2* const bm2l, 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* const bm2r); 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void bm2_print(const struct bitmap2* const bm2); 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Local variables. */ 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 48663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengstatic OSet* s_bm2_set_template; 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic ULong s_bitmap_creation_count; 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic ULong s_bitmap_merge_count; 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic ULong s_bitmap2_merge_count; 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Function definitions. */ 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 56663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengvoid DRD_(bm_module_init)(void) 57663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng{ 58663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng tl_assert(!s_bm2_set_template); 59663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng s_bm2_set_template 60663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng = VG_(OSetGen_Create_With_Pool)(0, 0, VG_(malloc), "drd.bitmap.bn.2", 61663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng VG_(free), 512, sizeof(struct bitmap2)); 62663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng} 63663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 64663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengvoid DRD_(bm_module_cleanup)(void) 65663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng{ 66663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng tl_assert(s_bm2_set_template); 67663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng VG_(OSetGen_Destroy)(s_bm2_set_template); 68663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng s_bm2_set_template = NULL; 69663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng} 70663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstruct bitmap* DRD_(bm_new)() 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap* bm; 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If this assert fails, fix the definition of BITS_PER_BITS_PER_UWORD */ 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* in drd_bitmap.h. */ 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert((1 << BITS_PER_BITS_PER_UWORD) == BITS_PER_UWORD); 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm = VG_(malloc)("drd.bitmap.bn.1", sizeof(*bm)); 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_init)(bm); 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm; 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_delete)(struct bitmap* const bm) 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_cleanup)(bm); 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(free)(bm); 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Initialize *bm. */ 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_init)(struct bitmap* const bm) 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned i; 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Cache initialization. a1 is initialized with a value that never can 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * match any valid address: the upper (ADDR_LSB_BITS + ADDR_IGNORED_BITS) 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * bits of a1 are always zero for a valid cache entry. 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < DRD_BITMAP_N_CACHE_ELEM; i++) 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm->cache[i].a1 = ~(UWord)1; 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm->cache[i].bm2 = 0; 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 109663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng bm->oset = VG_(OSetGen_EmptyClone)(s_bm2_set_template); 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s_bitmap_creation_count++; 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Free the memory allocated by DRD_(bm_init)(). */ 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_cleanup)(struct bitmap* const bm) 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Destroy)(bm->oset); 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Record an access of type access_type at addresses a .. a + size - 1 in 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * bitmap bm. 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @note The current implementation of bm_access_range does not work for the 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * highest addresses in the address range. At least on Linux this is 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * not a problem since the upper part of the address space is reserved 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * for the kernel. 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_range)(struct bitmap* const bm, 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2, 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const BmAccessTypeT access_type) 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(access_type == eLoad || access_type == eStore); 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (access_type == eLoad) 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_access_range_load)(bm, a1, a2); 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_access_range_store)(bm, a1, a2); 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_range_load)(struct bitmap* const bm, Addr a1, Addr a2) 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= a2); 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a2 < first_address_with_higher_msb(a2)); 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 == first_address_with_same_lsb(a1)); 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a2 == first_address_with_same_lsb(a2)); 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_start; 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_end; 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2; 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord b0; 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b)); 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2); 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a1) 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = a1; 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a2) 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = make_address(bm2->addr, 0); 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr + 1, 0) < a2) 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = make_address(bm2->addr + 1, 0); 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = a2; 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2); 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(address_msb(b_start) == address_msb(b_end - 1)); 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0) 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned k; 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2->bm1.bm0_r[k] = ~(UWord)0; 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_set(bm2->bm1.bm0_r, b0); 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_load_1)(struct bitmap* const bm, const Addr a1) 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_load(bm, a1, 1); 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_load_2)(struct bitmap* const bm, const Addr a1) 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 1) == 0) 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_load(bm, a1, 2); 212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_access_range)(bm, a1, a1 + 2, eLoad); 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_load_4)(struct bitmap* const bm, const Addr a1) 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 3) == 0) 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_load(bm, a1, 4); 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_access_range)(bm, a1, a1 + 4, eLoad); 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_load_8)(struct bitmap* const bm, const Addr a1) 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 7) == 0) 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_load(bm, a1, 8); 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if ((a1 & 3) == 0) 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_load(bm, a1 + 0, 4); 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_load(bm, a1 + 4, 4); 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_access_range)(bm, a1, a1 + 8, eLoad); 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_range_store)(struct bitmap* const bm, 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2) 239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= a2); 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a2 < first_address_with_higher_msb(a2)); 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 == first_address_with_same_lsb(a1)); 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a2 == first_address_with_same_lsb(a2)); 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_start; 251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_end; 252ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2; 253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord b0; 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b)); 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2); 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a1) 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = a1; 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a2) 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = make_address(bm2->addr, 0); 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr + 1, 0) < a2) 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = make_address(bm2->addr + 1, 0); 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = a2; 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2); 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(address_msb(b_start) == address_msb(b_end - 1)); 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0) 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned k; 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2->bm1.bm0_w[k] = ~(UWord)0; 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_set(bm2->bm1.bm0_w, b0); 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_store_1)(struct bitmap* const bm, const Addr a1) 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_store(bm, a1, 1); 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_store_2)(struct bitmap* const bm, const Addr a1) 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 1) == 0) 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_store(bm, a1, 2); 309ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 310ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_access_range)(bm, a1, a1 + 2, eStore); 311ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_store_4)(struct bitmap* const bm, const Addr a1) 314ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 3) == 0) 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_store(bm, a1, 4); 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_access_range)(bm, a1, a1 + 4, eStore); 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_access_store_8)(struct bitmap* const bm, const Addr a1) 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 323ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 7) == 0) 324ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_store(bm, a1, 8); 325ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if ((a1 & 3) == 0) 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_store(bm, a1 + 0, 4); 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_access_aligned_store(bm, a1 + 4, 4); 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_access_range)(bm, a1, a1 + 8, eStore); 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_has)(struct bitmap* const bm, const Addr a1, const Addr a2, 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const BmAccessTypeT access_type) 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(access_type == eLoad || access_type == eStore); 338ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 339ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (access_type == eLoad) 340ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_any_load)(bm, a1, a2); 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_any_store)(bm, a1, a2); 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 345663860b1408516d02ebfcb3a9999a134e6cfb223Ben ChengBool DRD_(bm_has_any_load_g)(struct bitmap* const bm) 346663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng{ 347663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng struct bitmap2* bm2; 348663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 349663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng tl_assert(bm); 350663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 351663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng VG_(OSetGen_ResetIter)(bm->oset); 352663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng for ( ; (bm2 = VG_(OSetGen_Next)(bm->oset)) != NULL; ) { 353663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng Addr b_start; 354663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng Addr b_end; 355663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng UWord b0; 356663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng const struct bitmap1* const p1 = &bm2->bm1; 357663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 358663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng b_start = make_address(bm2->addr, 0); 359663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng b_end = make_address(bm2->addr + 1, 0); 360663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 361663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 362663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng if (bm0_is_set(p1->bm0_r, b0)) 363663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng return True; 364663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng } 365663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng return False; 366663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng} 367663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownDRD_(bm_has_any_load)(struct bitmap* const bm, const Addr a1, const Addr a2) 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 374ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 375ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b)); 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 379ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 380ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 381ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 382ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 383ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 384ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 385ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2) 386ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 387ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_start; 388ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_end; 389ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord b0; 390ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap1* const p1 = &bm2->bm1; 391ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 392ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a1) 393ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = a1; 394ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 395ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a2) 396ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = make_address(bm2->addr, 0); 397ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 398ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 399ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_start && b_start <= a2); 400ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 401ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr + 1, 0) < a2) 402ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = make_address(bm2->addr + 1, 0); 403ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 404ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = a2; 405ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_end && b_end <= a2); 406ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(b_start < b_end); 407ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 408ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 409ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 410ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 411ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm0_is_set(p1->bm0_r, b0)) 412ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 413ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 414ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 415ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 416ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 417ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 418ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 419ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 420ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 421ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_has_any_store)(struct bitmap* const bm, 422ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2) 423ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 424ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 425ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 426ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 427ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 428ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 429ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 430ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b)); 431ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 432ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 433ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 434ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 435ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 436ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 437ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 438ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2) 439ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 440ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_start; 441ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_end; 442ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord b0; 443ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap1* const p1 = &bm2->bm1; 444ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 445ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a1) 446ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = a1; 447ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 448ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a2) 449ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = make_address(bm2->addr, 0); 450ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 451ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 452ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_start && b_start <= a2); 453ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 454ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr + 1, 0) < a2) 455ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = make_address(bm2->addr + 1, 0); 456ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 457ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = a2; 458ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_end && b_end <= a2); 459ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(b_start < b_end); 460ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 461ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 462ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 463ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 464ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm0_is_set(p1->bm0_w, b0)) 465ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 466ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 467ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 468ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 469ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 470ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 471ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 472ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 473ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 474ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Return True if there is a read access, write access or both */ 475ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* to any of the addresses in the range [ a1, a2 [ in bitmap bm. */ 476ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_has_any_access)(struct bitmap* const bm, 477ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2) 478ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 479ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 480ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 481ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 482ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 483ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 484ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 485ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b)); 486ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 487ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 488ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 489ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 490ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 491ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 492ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 493ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2) 494ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 495ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_start; 496ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_end; 497ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord b0; 498ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap1* const p1 = &bm2->bm1; 499ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 500ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a1) 501ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = a1; 502ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 503ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a2) 504ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = make_address(bm2->addr, 0); 505ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 506ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 507ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_start && b_start <= a2); 508ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 509ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr + 1, 0) < a2) 510ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = make_address(bm2->addr + 1, 0); 511ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 512ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = a2; 513ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_end && b_end <= a2); 514ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(b_start < b_end); 515ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 516ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 517ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 518ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 519ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* 520ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Note: the statement below uses a binary or instead of a logical 521ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * or on purpose. 522ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 523ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm0_is_set(p1->bm0_r, b0) | bm0_is_set(p1->bm0_w, b0)) 524ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 525ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 526ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 527ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 528ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 529ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 530ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 531ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 532ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 533ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 534ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Report whether an access of type access_type at address a is recorded in 535ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * bitmap bm. 536ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 537ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_has_1)(struct bitmap* const bm, 538ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a, const BmAccessTypeT access_type) 539ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 540ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* p2; 541ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap1* p1; 542ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UWord* p0; 543ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UWord a0 = address_lsb(a); 544ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 545ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 546ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 547ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p2 = bm2_lookup(bm, address_msb(a)); 548ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (p2) 549ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 550ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p1 = &p2->bm1; 551ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p0 = (access_type == eLoad) ? p1->bm0_r : p1->bm0_w; 552ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm0_is_set(p0, a0) ? True : False; 553ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 554ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 555ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 556ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 557ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_clear)(struct bitmap* const bm, Addr a1, Addr a2) 558ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 559ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 560ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 561ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 562ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1); 563ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= a2); 564ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 == first_address_with_same_lsb(a1)); 565ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a2 == first_address_with_same_lsb(a2)); 566ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 567ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 568ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 569ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* p2; 570ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c; 571ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 572ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 573ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b < a2); 574ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 575ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 576ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p2 = bm2_lookup_exclusive(bm, address_msb(b)); 577ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 578ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 579ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 580ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 581ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 582ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 583ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 584ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (p2 == 0) 585ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown continue; 586ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 587ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = b; 588ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If the first address in the bitmap that must be cleared does not */ 589ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* start on an UWord boundary, start clearing the first addresses. */ 590ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (uword_lsb(address_lsb(c))) 591ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 592ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c_next = first_address_with_higher_uword_msb(c); 593ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c_next > b_next) 594ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c_next = b_next; 595ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 596ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next 597ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && b_next <= a2); 598ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 599ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(c_next - c)); 600ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(c_next - c)); 601ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = c_next; 602ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 603ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If some UWords have to be cleared entirely, do this now. */ 604ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (uword_lsb(address_lsb(c)) == 0) 605ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 606ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c_next = first_address_with_same_uword_lsb(b_next); 607ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 608ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(uword_lsb(address_lsb(c)) == 0); 609ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(uword_lsb(address_lsb(c_next)) == 0); 610ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(c_next <= b_next); 611ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 612ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c_next > c) 613ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 614ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord idx = uword_msb(address_lsb(c)); 615ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(&p2->bm1.bm0_r[idx], 0, SCALED_SIZE((c_next - c) / 8)); 616ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(&p2->bm1.bm0_w[idx], 0, SCALED_SIZE((c_next - c) / 8)); 617ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = c_next; 618ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 619ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 620ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If the last address in the bitmap that must be cleared does not */ 621ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* fall on an UWord boundary, clear the last addresses. */ 622ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 623ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 624ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 625ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(b_next - c)); 626ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(b_next - c)); 627ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 628ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 629ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 630ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 631ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Clear all references to loads in bitmap bm starting at address a1 and 632ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * up to but not including address a2. 633ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 634ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_clear_load)(struct bitmap* const bm, Addr a1, Addr a2) 635ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 636ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 637ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 638ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 639ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1); 640ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= a2); 641ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 == first_address_with_same_lsb(a1)); 642ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a2 == first_address_with_same_lsb(a2)); 643ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 644ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 645ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 646ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* p2; 647ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c; 648ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 649ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 650ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b < a2); 651ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 652ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 653ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p2 = bm2_lookup_exclusive(bm, address_msb(b)); 654ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 655ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 656ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 657ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 658ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 659ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 660ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 661ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (p2 == 0) 662ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown continue; 663ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 664ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = b; 665ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If the first address in the bitmap that must be cleared does not */ 666ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* start on an UWord boundary, start clearing the first addresses. */ 667ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 668ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c < b_next && b_next <= a2); 669ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 670ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (uword_lsb(address_lsb(c))) 671ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 672ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c_next = first_address_with_higher_uword_msb(c); 673ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c_next > b_next) 674ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c_next = b_next; 675ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 676ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c < c_next && c_next <= b_next 677ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && b_next <= a2); 678ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 679ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(c_next - c)); 680ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = c_next; 681ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 682ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If some UWords have to be cleared entirely, do this now. */ 683ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 684ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 685ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 686ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (uword_lsb(address_lsb(c)) == 0) 687ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 688ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c_next = first_address_with_same_uword_lsb(b_next); 689ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 690ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(uword_lsb(address_lsb(c)) == 0); 691ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(uword_lsb(address_lsb(c_next)) == 0); 692ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next 693ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && b_next <= a2); 694ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 695ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c_next > c) 696ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 697ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord idx = uword_msb(address_lsb(c)); 698ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(&p2->bm1.bm0_r[idx], 0, SCALED_SIZE((c_next - c) / 8)); 699ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = c_next; 700ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 701ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 702ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If the last address in the bitmap that must be cleared does not */ 703ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* fall on an UWord boundary, clear the last addresses. */ 704ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 705ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 706ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 707ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(b_next - c)); 708ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 709ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 710ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 711ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 712ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Clear all references to stores in bitmap bm starting at address a1 and 713ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * up to but not including address a2. 714ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 715ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_clear_store)(struct bitmap* const bm, 716ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2) 717ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 718ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 719ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 720ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 721ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1); 722ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= a2); 723ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 == first_address_with_same_lsb(a1)); 724ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a2 == first_address_with_same_lsb(a2)); 725ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 726ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 727ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 728ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* p2; 729ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c; 730ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 731ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 732ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b < a2); 733ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 734ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 735ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p2 = bm2_lookup_exclusive(bm, address_msb(b)); 736ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 737ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 738ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 739ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 740ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 741ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 742ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 743ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (p2 == 0) 744ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown continue; 745ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 746ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = b; 747ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If the first address in the bitmap that must be cleared does not */ 748ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* start on an UWord boundary, start clearing the first addresses. */ 749ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 750ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c < b_next && b_next <= a2); 751ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 752ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (uword_lsb(address_lsb(c))) 753ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 754ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c_next = first_address_with_higher_uword_msb(c); 755ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c_next > b_next) 756ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c_next = b_next; 757ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 758ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c < c_next && c_next <= b_next 759ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && b_next <= a2); 760ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 761ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(c_next - c)); 762ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = c_next; 763ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 764ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If some UWords have to be cleared entirely, do this now. */ 765ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 766ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 767ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 768ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (uword_lsb(address_lsb(c)) == 0) 769ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 770ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr c_next = first_address_with_same_uword_lsb(b_next); 771ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 772ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(uword_lsb(address_lsb(c)) == 0); 773ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(uword_lsb(address_lsb(c_next)) == 0); 774ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next 775ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && b_next <= a2); 776ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 777ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c_next > c) 778ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 779ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord idx = uword_msb(address_lsb(c)); 780ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(&p2->bm1.bm0_w[idx], 0, SCALED_SIZE((c_next - c) / 8)); 781ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c = c_next; 782ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 783ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 784ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* If the last address in the bitmap that must be cleared does not */ 785ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* fall on an UWord boundary, clear the last addresses. */ 786ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 787ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 788ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 789ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(b_next - c)); 790ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 791ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 792ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 793ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 794ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Clear bitmap bm starting at address a1 and up to but not including address 795ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * a2. Return True if and only if any of the addresses was set before 796ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * clearing. 797ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 798ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_test_and_clear)(struct bitmap* const bm, 799ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2) 800ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 801ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool result; 802ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 803ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown result = DRD_(bm_has_any_access)(bm, a1, a2) != 0; 804ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_(bm_clear)(bm, a1, a2); 805ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return result; 806ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 807ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 808ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_has_conflict_with)(struct bitmap* const bm, 809ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2, 810ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const BmAccessTypeT access_type) 811ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 812ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b, b_next; 813ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 814ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm); 815ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 816ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = a1; b < a2; b = b_next) 817ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 818ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b)); 819ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 820ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = first_address_with_higher_msb(b); 821ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (b_next > a2) 822ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 823ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_next = a2; 824ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 825ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 826ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2) 827ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 828ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_start; 829ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr b_end; 830ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord b0; 831ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap1* const p1 = &bm2->bm1; 832ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 833ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a1) 834ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = a1; 835ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 836ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr, 0) < a2) 837ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_start = make_address(bm2->addr, 0); 838ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 839ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 840ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_start && b_start <= a2); 841ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 842ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (make_address(bm2->addr + 1, 0) < a2) 843ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = make_address(bm2->addr + 1, 0); 844ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 845ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b_end = a2; 846ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(a1 <= b_end && b_end <= a2); 847ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(b_start < b_end); 848ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 849ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 850ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 851ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 852ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (access_type == eLoad) 853ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 854ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm0_is_set(p1->bm0_w, b0)) 855ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 856ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 857ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 858ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 859ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 860ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 861ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(access_type == eStore); 862ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm0_is_set(p1->bm0_r, b0) 863ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown | bm0_is_set(p1->bm0_w, b0)) 864ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 865ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 866ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 867ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 868ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 869ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 870ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 871ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 872ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 873ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 874ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_load_has_conflict_with)(struct bitmap* const bm, 875ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2) 876ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 877ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_conflict_with)(bm, a1, a2, eLoad); 878ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 879ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 880ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_load_1_has_conflict_with)(struct bitmap* const bm, const Addr a1) 881ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 882ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm_aligned_load_has_conflict_with(bm, a1, 1); 883ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 884ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 885ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_load_2_has_conflict_with)(struct bitmap* const bm, const Addr a1) 886ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 887ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 1) == 0) 888ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm_aligned_load_has_conflict_with(bm, a1, 2); 889ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 890ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_conflict_with)(bm, a1, a1 + 2, eLoad); 891ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 892ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 893ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_load_4_has_conflict_with)(struct bitmap* const bm, const Addr a1) 894ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 895ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 3) == 0) 896ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm_aligned_load_has_conflict_with(bm, a1, 4); 897ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 898ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_conflict_with)(bm, a1, a1 + 4, eLoad); 899ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 900ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 901ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_load_8_has_conflict_with)(struct bitmap* const bm, const Addr a1) 902ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 903ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 7) == 0) 904ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm_aligned_load_has_conflict_with(bm, a1, 8); 905ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 906ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_conflict_with)(bm, a1, a1 + 8, eLoad); 907ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 908ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 909ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_store_1_has_conflict_with)(struct bitmap* const bm, const Addr a1) 910ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 911ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm_aligned_store_has_conflict_with(bm, a1, 1); 912ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 913ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 914ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_store_2_has_conflict_with)(struct bitmap* const bm, const Addr a1) 915ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 916ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 1) == 0) 917ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm_aligned_store_has_conflict_with(bm, a1, 2); 918ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 919ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_conflict_with)(bm, a1, a1 + 2, eStore); 920ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 921ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 922ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_store_4_has_conflict_with)(struct bitmap* const bm, const Addr a1) 923ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 924ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 3) == 0) 925ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm_aligned_store_has_conflict_with(bm, a1, 4); 926ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 927ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_conflict_with)(bm, a1, a1 + 4, eStore); 928ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 929ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 930ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_store_8_has_conflict_with)(struct bitmap* const bm, const Addr a1) 931ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 932ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((a1 & 7) == 0) 933ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm_aligned_store_has_conflict_with(bm, a1, 8); 934ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 935ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_conflict_with)(bm, a1, a1 + 8, eStore); 936ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 937ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 938ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_store_has_conflict_with)(struct bitmap* const bm, 939ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Addr a1, const Addr a2) 940ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 941ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return DRD_(bm_has_conflict_with)(bm, a1, a2, eStore); 942ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 943ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 944ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 945ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Return True if the two bitmaps *lhs and *rhs are identical, and false 946ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * if not. 947ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 948ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_equal)(struct bitmap* const lhs, struct bitmap* const rhs) 949ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 950ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2l; 951ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2r; 952ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 953ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* It's not possible to have two independent iterators over the same OSet, */ 954ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* so complain if lhs == rhs. */ 955ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(lhs != rhs); 956ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 957ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(lhs->oset); 958ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(rhs->oset); 959ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 960ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for ( ; (bm2l = VG_(OSetGen_Next)(lhs->oset)) != 0; ) 961ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 962ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (bm2l 963ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && ! DRD_(bm_has_any_access)(lhs, 964ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2l->addr, 0), 965ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2l->addr + 1, 0))) 966ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 967ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2l = VG_(OSetGen_Next)(lhs->oset); 968ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 969ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2l == 0) 970ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 971ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2l); 972ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 973ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown do 974ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 975ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2r = VG_(OSetGen_Next)(rhs->oset); 976ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2r == 0) 977ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 978ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 979ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (! DRD_(bm_has_any_access)(rhs, 980ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2r->addr, 0), 981ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2r->addr + 1, 0))); 982ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 983ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2r); 984ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(DRD_(bm_has_any_access)(rhs, 985ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2r->addr, 0), 986ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2r->addr + 1, 0))); 987ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 988ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2l != bm2r 989ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && (bm2l->addr != bm2r->addr 990ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown || VG_(memcmp)(&bm2l->bm1, &bm2r->bm1, sizeof(bm2l->bm1)) != 0)) 991ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 992ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 993ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 994ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 995ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 996ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown do 997ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 998ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2r = VG_(OSetGen_Next)(rhs->oset); 999ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } while (bm2r && ! DRD_(bm_has_any_access)(rhs, 1000ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2r->addr, 0), 1001ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2r->addr + 1, 0))); 1002ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2r) 1003ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1004ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(DRD_(bm_has_any_access)(rhs, 1005ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2r->addr, 0), 1006ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(bm2r->addr + 1, 0))); 1007ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 1008ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1009ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 1010ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1011ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1012ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_swap)(struct bitmap* const bm1, struct bitmap* const bm2) 1013ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1014ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet* const tmp = bm1->oset; 1015ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm1->oset = bm2->oset; 1016ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2->oset = tmp; 1017ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1018ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1019ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Merge bitmaps *lhs and *rhs into *lhs. */ 1020ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_merge2)(struct bitmap* const lhs, struct bitmap* const rhs) 1021ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1022ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2l; 1023ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2r; 1024ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1025ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* 1026ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * It's not possible to have two independent iterators over the same OSet, 1027ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * so complain if lhs == rhs. 1028ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 1029ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(lhs != rhs); 1030ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1031ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s_bitmap_merge_count++; 1032ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1033ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(rhs->oset); 1034ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1035ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; ) 1036ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1037ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr); 1038ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2l) 1039ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1040ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2l != bm2r); 1041ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2_merge(bm2l, bm2r); 1042ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1043ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 1044ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1045ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2_insert_copy(lhs, bm2r); 1046ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1047ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1048ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1049ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1050ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Clear bitmap2::recalc. */ 1051ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_unmark)(struct bitmap* bm) 1052ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1053ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2; 1054ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1055ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (VG_(OSetGen_ResetIter)(bm->oset); 1056ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; 1057ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ) 1058ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1059ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2->recalc = False; 1060ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1061ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1062ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1063ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 1064ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Report whether bitmap2::recalc has been set for the second level bitmap 1065ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * corresponding to address a. 1066ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 1067ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool DRD_(bm_is_marked)(struct bitmap* bm, const Addr a) 1068ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1069ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* bm2; 1070ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1071ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2 = bm2_lookup(bm, a); 1072ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bm2 && bm2->recalc; 1073ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1074ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1075ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 1076ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Set bitmap2::recalc in bml for each second level bitmap in bmr that contains 1077ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * at least one access. 1078ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 1079ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @note Any new second-level bitmaps inserted in bml by this function are 1080ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * uninitialized. 1081ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 1082ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_mark)(struct bitmap* bml, struct bitmap* bmr) 1083ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1084ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2l; 1085ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2r; 1086ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1087ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (VG_(OSetGen_ResetIter)(bmr->oset); 1088ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (bm2r = VG_(OSetGen_Next)(bmr->oset)) != 0; 1089ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ) 1090ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1091b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov bm2l = bm2_lookup_or_insert(bml, bm2r->addr); 1092b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov bm2l->recalc = True; 1093ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1094ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1095ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1096ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Clear all second-level bitmaps for which bitmap2::recalc == True. */ 1097ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_clear_marked)(struct bitmap* bm) 1098ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1099ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2; 1100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (VG_(OSetGen_ResetIter)(bm->oset); 1102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; 1103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ) 1104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2->recalc) 1106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2_clear(bm2); 1107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Merge the second level bitmaps from *rhs into *lhs for which recalc == True. */ 1111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_merge2_marked)(struct bitmap* const lhs, struct bitmap* const rhs) 1112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2l; 1114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2r; 1115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* 1117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * It's not possible to have two independent iterators over the same OSet, 1118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * so complain if lhs == rhs. 1119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 1120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(lhs != rhs); 1121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s_bitmap_merge_count++; 1123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(rhs->oset); 1125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; ) 1127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr); 1129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2l && bm2l->recalc) 1130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2l != bm2r); 1132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2_merge(bm2l, bm2r); 1133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Remove all marked second-level bitmaps that do not contain any access. */ 1138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_remove_cleared_marked)(struct bitmap* bm) 1139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2; 1141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(bm->oset); 1143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for ( ; (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; ) 1144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UWord a1 = bm2->addr; 1146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2->recalc 1147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && ! DRD_(bm_has_any_access(bm, make_address(a1, 0), 1148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown make_address(a1 + 1, 0)))) 1149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2_remove(bm, a1); 1151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIterAt)(bm->oset, &a1); 1152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 1157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Report whether there are any RW / WR / WW patterns in lhs and rhs. 1158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @param lhs First bitmap. 1159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @param rhs Bitmap to be compared with lhs. 1160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @return !=0 if there are data races, == 0 if there are none. 1161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 1162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownint DRD_(bm_has_races)(struct bitmap* const lhs, struct bitmap* const rhs) 1163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(lhs->oset); 1165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(rhs->oset); 1166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (;;) 1168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* bm2l; 1170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap2* bm2r; 1171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap1* bm1l; 1172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap1* bm1r; 1173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned k; 1174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2l = VG_(OSetGen_Next)(lhs->oset); 1176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2r = VG_(OSetGen_Next)(rhs->oset); 1177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (bm2l && bm2r && bm2l->addr != bm2r->addr) 1178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2l->addr < bm2r->addr) 1180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2l = VG_(OSetGen_Next)(lhs->oset); 1181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 1182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2r = VG_(OSetGen_Next)(rhs->oset); 1183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bm2l == 0 || bm2r == 0) 1185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 1186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm1l = &bm2l->bm1; 1188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm1r = &bm2r->bm1; 1189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 1191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned b; 1193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (b = 0; b < BITS_PER_UWORD; b++) 1194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord const access_mask 1196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown = ((bm1l->bm0_r[k] & bm0_mask(b)) ? LHS_R : 0) 1197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown | ((bm1l->bm0_w[k] & bm0_mask(b)) ? LHS_W : 0) 1198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown | ((bm1r->bm0_r[k] & bm0_mask(b)) ? RHS_R : 0) 1199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown | ((bm1r->bm0_w[k] & bm0_mask(b)) ? RHS_W : 0); 1200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr const a = make_address(bm2l->addr, k * BITS_PER_UWORD | b); 1201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (HAS_RACE(access_mask) && ! DRD_(is_suppressed)(a, a + 1)) 1202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 1; 1204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 1209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid DRD_(bm_print)(struct bitmap* const bm) 1212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct bitmap2* bm2; 1214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (VG_(OSetGen_ResetIter)(bm->oset); 1216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; 1217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ) 1218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2_print(bm2); 1220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void bm2_print(const struct bitmap2* const bm2) 1224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const struct bitmap1* bm1; 1226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr a; 1227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2); 1229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm1 = &bm2->bm1; 1231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (a = make_address(bm2->addr, 0); 1232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a <= make_address(bm2->addr + 1, 0) - 1; 1233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a++) 1234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Bool r = bm0_is_set(bm1->bm0_r, address_lsb(a)) != 0; 1236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Bool w = bm0_is_set(bm1->bm0_w, address_lsb(a)) != 0; 1237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (r || w) 1238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(printf)("0x%08lx %c %c\n", 1240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a, 1241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown w ? 'W' : ' ', 1242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown r ? 'R' : ' '); 1243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownULong DRD_(bm_get_bitmap_creation_count)(void) 1248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return s_bitmap_creation_count; 1250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1252ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownULong DRD_(bm_get_bitmap2_creation_count)(void) 1253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return s_bitmap2_creation_count; 1255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownULong DRD_(bm_get_bitmap2_merge_count)(void) 1258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return s_bitmap2_merge_count; 1260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** Compute *bm2l |= *bm2r. */ 1263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 1264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid bm2_merge(struct bitmap2* const bm2l, const struct bitmap2* const bm2r) 1265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 1266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned k; 1267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2l); 1269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2r); 1270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bm2l->addr == bm2r->addr); 1271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s_bitmap2_merge_count++; 1273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 1275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2l->bm1.bm0_r[k] |= bm2r->bm1.bm0_r[k]; 1277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 1279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 1280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm2l->bm1.bm0_w[k] |= bm2r->bm1.bm0_w[k]; 1281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 1282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 1283