1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- Callgrind ---*/ 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- bb.c ---*/ 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This file is part of Callgrind, a Valgrind tool for call tracing. 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 9436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Copyright (C) 2002-2013, Josef Weidendorfer (Josef.Weidendorfer@gmx.de) 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is free software; you can redistribute it and/or 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown modify it under the terms of the GNU General Public License as 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown published by the Free Software Foundation; either version 2 of the 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown License, or (at your option) any later version. 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is distributed in the hope that it will be useful, but 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WITHOUT ANY WARRANTY; without even the implied warranty of 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown General Public License for more details. 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown You should have received a copy of the GNU General Public License 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown along with this program; if not, write to the Free Software 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 02111-1307, USA. 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown The GNU General Public License is contained in the file COPYING. 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "global.h" 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*------------------------------------------------------------*/ 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- Basic block (BB) operations ---*/ 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*------------------------------------------------------------*/ 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* BB hash, resizable */ 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbb_hash bbs; 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid CLG_(init_bb_hash)() 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.size = 8437; 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.entries = 0; 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.table = (BB**) CLG_MALLOC("cl.bb.ibh.1", 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.size * sizeof(BB*)); 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < bbs.size; i++) bbs.table[i] = NULL; 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbb_hash* CLG_(get_bb_hash)() 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return &bbs; 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* The hash stores BBs according to 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * - ELF object (is 0 for code in anonymous mapping) 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * - BB base as object file offset 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic __inline__ 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUInt bb_hash_idx(obj_node* obj, PtrdiffT offset, UInt size) 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (((Addr)obj) + offset) % size; 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* double size of bb table */ 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid resize_bb_table(void) 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i, new_size, conflicts1 = 0, conflicts2 = 0; 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BB **new_table, *curr, *next; 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UInt new_idx; 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_size = 2* bbs.size +3; 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_table = (BB**) CLG_MALLOC("cl.bb.rbt.1", 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_size * sizeof(BB*)); 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!new_table) return; 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < new_size; i++) 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_table[i] = NULL; 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < bbs.size; i++) { 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bbs.table[i] == NULL) continue; 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown curr = bbs.table[i]; 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (NULL != curr) { 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown next = curr->next; 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_idx = bb_hash_idx(curr->obj, curr->offset, new_size); 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown curr->next = new_table[new_idx]; 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown new_table[new_idx] = curr; 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (curr->next) { 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown conflicts1++; 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (curr->next->next) 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown conflicts2++; 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown curr = next; 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(free)(bbs.table); 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(0, "Resize BB Hash: %d => %d (entries %d, conflicts %d/%d)\n", 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.size, new_size, 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.entries, conflicts1, conflicts2); 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.size = new_size; 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.table = new_table; 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_(stat).bb_hash_resizes++; 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Allocate new BB structure (including space for event type list) 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Not initialized: 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * - instr_len, cost_count, instr[] 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic BB* new_bb(obj_node* obj, PtrdiffT offset, 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UInt instr_count, UInt cjmp_count, Bool cjmp_inverted) 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BB* bb; 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UInt idx, size; 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* check fill degree of bb hash table and resize if needed (>80%) */ 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.entries++; 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (10 * bbs.entries / bbs.size > 8) 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown resize_bb_table(); 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown size = sizeof(BB) + instr_count * sizeof(InstrInfo) 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown + (cjmp_count+1) * sizeof(CJmpInfo); 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb = (BB*) CLG_MALLOC("cl.bb.nb.1", size); 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(bb, 0, size); 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->obj = obj; 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->offset = offset; 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->instr_count = instr_count; 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->cjmp_count = cjmp_count; 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->cjmp_inverted = cjmp_inverted; 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->jmp = (CJmpInfo*) &(bb->instr[instr_count]); 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->instr_len = 0; 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->cost_count = 0; 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->sect_kind = VG_(DebugInfo_sect_kind)(NULL, 0, offset + obj->offset); 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->fn = 0; 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->line = 0; 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->is_entry = 0; 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->bbcc_list = 0; 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->last_bbcc = 0; 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* insert into BB hash table */ 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown idx = bb_hash_idx(obj, offset, bbs.size); 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->next = bbs.table[idx]; 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.table[idx] = bb; 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_(stat).distinct_bbs++; 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#if CLG_ENABLE_DEBUG 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUGIF(3) { 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(printf)(" new_bb (instr %d, jmps %d, inv %s) [now %d]: ", 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown instr_count, cjmp_count, 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cjmp_inverted ? "yes":"no", 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_(stat).distinct_bbs); 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_(print_bb)(0, bb); 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(printf)("\n"); 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_(get_fn_node)(bb); 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bb; 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* get the BB structure for a BB start address */ 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic __inline__ 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBB* lookup_bb(obj_node* obj, PtrdiffT offset) 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BB* bb; 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int idx; 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown idx = bb_hash_idx(obj, offset, bbs.size); 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb = bbs.table[idx]; 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while(bb) { 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((bb->obj == obj) && (bb->offset == offset)) break; 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb = bb->next; 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(5, " lookup_bb (Obj %s, off %#lx): %p\n", 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj->name, offset, bb); 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bb; 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic __inline__ 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownobj_node* obj_of_address(Addr addr) 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj_node* obj; 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DebugInfo* di; 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown PtrdiffT offset; 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown di = VG_(find_DebugInfo)(addr); 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj = CLG_(get_obj_node)( di ); 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Update symbol offset in object if remapped */ 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* FIXME (or at least check this) 2008 Feb 19: 'offset' is 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown only correct for text symbols, not for data symbols */ 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown offset = di ? VG_(DebugInfo_get_text_bias)(di):0; 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (obj->offset != offset) { 212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr start = di ? VG_(DebugInfo_get_text_avma)(di) : 0; 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(0, "Mapping changed for '%s': %#lx -> %#lx\n", 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj->name, obj->start, start); 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Size should be the same, and offset diff == start diff */ 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_ASSERT( obj->size == (di ? VG_(DebugInfo_get_text_size)(di) : 0) ); 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_ASSERT( obj->start - start == obj->offset - offset ); 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj->offset = offset; 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj->start = start; 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return obj; 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Get the BB structure for a BB start address. 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * If the BB has to be created, the IRBB is needed to 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * compute the event type list for costs, and seen_before is 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * set to False. Otherwise, seen_before is set to True. 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * BBs are never discarded. There are 2 cases where this function 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * is called from CLG_(instrument)() and a BB already exists: 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * - The instrumented version was removed from Valgrinds TT cache 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * - The ELF object of the BB was unmapped and mapped again. 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * This involves a possibly different address, but is handled by 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * looking up a BB keyed by (obj_node, file offset). 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * bbIn==0 is possible for artifical BB without real code. 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Such a BB is created when returning to an unknown function. 241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBB* CLG_(get_bb)(Addr addr, IRSB* bbIn, /*OUT*/ Bool *seen_before) 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BB* bb; 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj_node* obj; 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UInt n_instrs, n_jmps; 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool cjmp_inverted = False; 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(5, "+ get_bb(BB %#lx)\n", addr); 250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj = obj_of_address(addr); 252ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb = lookup_bb(obj, addr - obj->offset); 253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n_instrs = 0; 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n_jmps = 0; 256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_(collectBlockInfo)(bbIn, &n_instrs, &n_jmps, &cjmp_inverted); 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *seen_before = bb ? True : False; 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*seen_before) { 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bb->instr_count != n_instrs) { 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(message)(Vg_DebugMsg, 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown "ERROR: BB Retranslation Mismatch at BB %#lx\n", addr); 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(message)(Vg_DebugMsg, 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown " new: Obj %s, Off %#lx, BBOff %#lx, Instrs %u\n", 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj->name, obj->offset, 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown addr - obj->offset, n_instrs); 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(message)(Vg_DebugMsg, 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown " old: Obj %s, Off %#lx, BBOff %#lx, Instrs %u\n", 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->obj->name, bb->obj->offset, 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb->offset, bb->instr_count); 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_ASSERT(bb->instr_count == n_instrs ); 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_ASSERT(bb->cjmp_count == n_jmps ); 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_(stat).bb_retranslations++; 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(5, "- get_bb(BB %#lx): seen before.\n", addr); 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bb; 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb = new_bb(obj, addr - obj->offset, n_instrs, n_jmps, cjmp_inverted); 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(5, "- get_bb(BB %#lx)\n", addr); 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bb; 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Delete the BB info for the bb with unredirected entry-point 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown address 'addr'. */ 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid CLG_(delete_bb)(Addr addr) 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BB *bb, *bp; 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int idx, size; 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj_node* obj = obj_of_address(addr); 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown PtrdiffT offset = addr - obj->offset; 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown idx = bb_hash_idx(obj, offset, bbs.size); 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb = bbs.table[idx]; 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* bb points at the current bb under consideration, and bp is the 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown one before. */ 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bp = NULL; 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while(bb) { 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((bb->obj == obj) && (bb->offset == offset)) break; 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bp = bb; 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bb = bb->next; 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 309ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bb == NULL) { 310ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(3, " delete_bb (Obj %s, off %#lx): NOT FOUND\n", 311ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj->name, offset); 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* we didn't find it. 314ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * this happens when callgrinds instrumentation mode 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * was off at BB translation time, ie. no BB was created. 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* unlink it from hash table */ 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bp == NULL) { 323ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* we found the first one in the list. */ 324ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bb == bbs.table[idx]); 325ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bbs.table[idx] = bb->next; 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(bb != bbs.table[idx]); 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bp->next = bb->next; 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(3, " delete_bb (Obj %s, off %#lx): %p, BBCC head: %p\n", 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown obj->name, offset, bb, bb->bbcc_list); 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bb->bbcc_list == 0) { 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* can be safely deleted */ 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Fill the block up with junk and then free it, so we will 338ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown hopefully get a segfault if it is used again by mistake. */ 339ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown size = sizeof(BB) 340ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown + bb->instr_count * sizeof(InstrInfo) 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown + (bb->cjmp_count+1) * sizeof(CJmpInfo); 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)( bb, 0xAA, size ); 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_FREE(bb); 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 345ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 346ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CLG_DEBUG(3, " delete_bb: BB in use, can not free!\n"); 347ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 348