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