1 /*--------------------------------------------------------------------*/ 2 /*--- Callgrind ---*/ 3 /*--- bbcc.c ---*/ 4 /*--------------------------------------------------------------------*/ 5 6 /* 7 This file is part of Callgrind, a Valgrind tool for call tracing. 8 9 Copyright (C) 2002-2017, Josef Weidendorfer (Josef.Weidendorfer (at) gmx.de) 10 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 #include "costs.h" 31 32 #include "pub_tool_threadstate.h" 33 34 /*------------------------------------------------------------*/ 35 /*--- BBCC operations ---*/ 36 /*------------------------------------------------------------*/ 37 38 #define N_BBCC_INITIAL_ENTRIES 10437 39 40 /* BBCC table (key is BB/Context), per thread, resizable */ 41 bbcc_hash current_bbccs; 42 43 void CLG_(init_bbcc_hash)(bbcc_hash* bbccs) 44 { 45 Int i; 46 47 CLG_ASSERT(bbccs != 0); 48 49 bbccs->size = N_BBCC_INITIAL_ENTRIES; 50 bbccs->entries = 0; 51 bbccs->table = (BBCC**) CLG_MALLOC("cl.bbcc.ibh.1", 52 bbccs->size * sizeof(BBCC*)); 53 54 for (i = 0; i < bbccs->size; i++) bbccs->table[i] = NULL; 55 } 56 57 void CLG_(copy_current_bbcc_hash)(bbcc_hash* dst) 58 { 59 CLG_ASSERT(dst != 0); 60 61 dst->size = current_bbccs.size; 62 dst->entries = current_bbccs.entries; 63 dst->table = current_bbccs.table; 64 } 65 66 bbcc_hash* CLG_(get_current_bbcc_hash)() 67 { 68 return ¤t_bbccs; 69 } 70 71 void CLG_(set_current_bbcc_hash)(bbcc_hash* h) 72 { 73 CLG_ASSERT(h != 0); 74 75 current_bbccs.size = h->size; 76 current_bbccs.entries = h->entries; 77 current_bbccs.table = h->table; 78 } 79 80 /* 81 * Zero all costs of a BBCC 82 */ 83 void CLG_(zero_bbcc)(BBCC* bbcc) 84 { 85 Int i; 86 jCC* jcc; 87 88 CLG_ASSERT(bbcc->cxt != 0); 89 CLG_DEBUG(1, " zero_bbcc: BB %#lx, Cxt %u " 90 "(fn '%s', rec %u)\n", 91 bb_addr(bbcc->bb), 92 bbcc->cxt->base_number + bbcc->rec_index, 93 bbcc->cxt->fn[0]->name, 94 bbcc->rec_index); 95 96 if ((bbcc->ecounter_sum ==0) && 97 (bbcc->ret_counter ==0)) return; 98 99 for(i=0;i<bbcc->bb->cost_count;i++) 100 bbcc->cost[i] = 0; 101 for(i=0;i <= bbcc->bb->cjmp_count;i++) { 102 bbcc->jmp[i].ecounter = 0; 103 for(jcc=bbcc->jmp[i].jcc_list; jcc; jcc=jcc->next_from) 104 CLG_(init_cost)( CLG_(sets).full, jcc->cost ); 105 } 106 bbcc->ecounter_sum = 0; 107 bbcc->ret_counter = 0; 108 } 109 110 111 112 void CLG_(forall_bbccs)(void (*func)(BBCC*)) 113 { 114 BBCC *bbcc, *bbcc2; 115 int i, j; 116 117 for (i = 0; i < current_bbccs.size; i++) { 118 if ((bbcc=current_bbccs.table[i]) == NULL) continue; 119 while (bbcc) { 120 /* every bbcc should have a rec_array */ 121 CLG_ASSERT(bbcc->rec_array != 0); 122 123 for(j=0;j<bbcc->cxt->fn[0]->separate_recursions;j++) { 124 if ((bbcc2 = bbcc->rec_array[j]) == 0) continue; 125 126 (*func)(bbcc2); 127 } 128 bbcc = bbcc->next; 129 } 130 } 131 } 132 133 134 /* All BBCCs for recursion level 0 are inserted into a 135 * thread specific hash table with key 136 * - address of BB structure (unique, as never freed) 137 * - current context (includes caller chain) 138 * BBCCs for other recursion levels are in bbcc->rec_array. 139 * 140 * The hash is used in setup_bb(), i.e. to find the cost 141 * counters to be changed in the execution of a BB. 142 */ 143 144 static __inline__ 145 UInt bbcc_hash_idx(BB* bb, Context* cxt, UInt size) 146 { 147 CLG_ASSERT(bb != 0); 148 CLG_ASSERT(cxt != 0); 149 150 return ((Addr)bb + (Addr)cxt) % size; 151 } 152 153 154 /* Lookup for a BBCC in hash. 155 */ 156 static 157 BBCC* lookup_bbcc(BB* bb, Context* cxt) 158 { 159 BBCC* bbcc = bb->last_bbcc; 160 UInt idx; 161 162 /* check LRU */ 163 if (bbcc->cxt == cxt) { 164 if (!CLG_(clo).separate_threads) { 165 /* if we don't dump threads separate, tid doesn't have to match */ 166 return bbcc; 167 } 168 if (bbcc->tid == CLG_(current_tid)) return bbcc; 169 } 170 171 CLG_(stat).bbcc_lru_misses++; 172 173 idx = bbcc_hash_idx(bb, cxt, current_bbccs.size); 174 bbcc = current_bbccs.table[idx]; 175 while (bbcc && 176 (bb != bbcc->bb || 177 cxt != bbcc->cxt)) { 178 bbcc = bbcc->next; 179 } 180 181 CLG_DEBUG(2," lookup_bbcc(BB %#lx, Cxt %u, fn '%s'): %p (tid %u)\n", 182 bb_addr(bb), cxt->base_number, cxt->fn[0]->name, 183 bbcc, bbcc ? bbcc->tid : 0); 184 185 CLG_DEBUGIF(2) 186 if (bbcc) CLG_(print_bbcc)(-2,bbcc); 187 188 return bbcc; 189 } 190 191 192 /* double size of hash table 1 (addr->BBCC) */ 193 static void resize_bbcc_hash(void) 194 { 195 Int i, new_size, conflicts1 = 0, conflicts2 = 0; 196 BBCC** new_table; 197 UInt new_idx; 198 BBCC *curr_BBCC, *next_BBCC; 199 200 new_size = 2*current_bbccs.size+3; 201 new_table = (BBCC**) CLG_MALLOC("cl.bbcc.rbh.1", 202 new_size * sizeof(BBCC*)); 203 204 for (i = 0; i < new_size; i++) 205 new_table[i] = NULL; 206 207 for (i = 0; i < current_bbccs.size; i++) { 208 if (current_bbccs.table[i] == NULL) continue; 209 210 curr_BBCC = current_bbccs.table[i]; 211 while (NULL != curr_BBCC) { 212 next_BBCC = curr_BBCC->next; 213 214 new_idx = bbcc_hash_idx(curr_BBCC->bb, 215 curr_BBCC->cxt, 216 new_size); 217 218 curr_BBCC->next = new_table[new_idx]; 219 new_table[new_idx] = curr_BBCC; 220 if (curr_BBCC->next) { 221 conflicts1++; 222 if (curr_BBCC->next->next) 223 conflicts2++; 224 } 225 226 curr_BBCC = next_BBCC; 227 } 228 } 229 230 VG_(free)(current_bbccs.table); 231 232 233 CLG_DEBUG(0,"Resize BBCC Hash: %u => %d (entries %u, conflicts %d/%d)\n", 234 current_bbccs.size, new_size, 235 current_bbccs.entries, conflicts1, conflicts2); 236 237 current_bbccs.size = new_size; 238 current_bbccs.table = new_table; 239 CLG_(stat).bbcc_hash_resizes++; 240 } 241 242 243 static __inline 244 BBCC** new_recursion(int size) 245 { 246 BBCC** bbccs; 247 int i; 248 249 bbccs = (BBCC**) CLG_MALLOC("cl.bbcc.nr.1", sizeof(BBCC*) * size); 250 for(i=0;i<size;i++) 251 bbccs[i] = 0; 252 253 CLG_DEBUG(3," new_recursion(size %d): %p\n", size, bbccs); 254 255 return bbccs; 256 } 257 258 259 /* 260 * Allocate a new BBCC 261 * 262 * Uninitialized: 263 * cxt, rec_index, rec_array, next_bbcc, next1, next2 264 */ 265 static __inline__ 266 BBCC* new_bbcc(BB* bb) 267 { 268 BBCC* bbcc; 269 Int i; 270 271 /* We need cjmp_count+1 JmpData structs: 272 * the last is for the unconditional jump/call/ret at end of BB 273 */ 274 bbcc = (BBCC*)CLG_MALLOC("cl.bbcc.nb.1", 275 sizeof(BBCC) + 276 (bb->cjmp_count+1) * sizeof(JmpData)); 277 bbcc->bb = bb; 278 bbcc->tid = CLG_(current_tid); 279 280 bbcc->ret_counter = 0; 281 bbcc->skipped = 0; 282 bbcc->cost = CLG_(get_costarray)(bb->cost_count); 283 for(i=0;i<bb->cost_count;i++) 284 bbcc->cost[i] = 0; 285 for(i=0; i<=bb->cjmp_count; i++) { 286 bbcc->jmp[i].ecounter = 0; 287 bbcc->jmp[i].jcc_list = 0; 288 } 289 bbcc->ecounter_sum = 0; 290 291 /* Init pointer caches (LRU) */ 292 bbcc->lru_next_bbcc = 0; 293 bbcc->lru_from_jcc = 0; 294 bbcc->lru_to_jcc = 0; 295 296 CLG_(stat).distinct_bbccs++; 297 298 CLG_DEBUG(3, " new_bbcc(BB %#lx): %p (now %d)\n", 299 bb_addr(bb), bbcc, CLG_(stat).distinct_bbccs); 300 301 return bbcc; 302 } 303 304 305 /** 306 * Inserts a new BBCC into hashes. 307 * BBCC specific items must be set as this is used for the hash 308 * keys: 309 * fn : current function 310 * tid : current thread ID 311 * from : position where current function is called from 312 * 313 * Recursion level doesn't need to be set as this is not included 314 * in the hash key: Only BBCCs with rec level 0 are in hashes. 315 */ 316 static 317 void insert_bbcc_into_hash(BBCC* bbcc) 318 { 319 UInt idx; 320 321 CLG_ASSERT(bbcc->cxt != 0); 322 323 CLG_DEBUG(3,"+ insert_bbcc_into_hash(BB %#lx, fn '%s')\n", 324 bb_addr(bbcc->bb), bbcc->cxt->fn[0]->name); 325 326 /* check fill degree of hash and resize if needed (>90%) */ 327 current_bbccs.entries++; 328 if (100 * current_bbccs.entries / current_bbccs.size > 90) 329 resize_bbcc_hash(); 330 331 idx = bbcc_hash_idx(bbcc->bb, bbcc->cxt, current_bbccs.size); 332 bbcc->next = current_bbccs.table[idx]; 333 current_bbccs.table[idx] = bbcc; 334 335 CLG_DEBUG(3,"- insert_bbcc_into_hash: %u entries\n", 336 current_bbccs.entries); 337 } 338 339 /* String is returned in a dynamically allocated buffer. Caller is 340 responsible for free'ing it. */ 341 static HChar* mangled_cxt(const Context* cxt, Int rec_index) 342 { 343 Int i, p; 344 345 if (!cxt) return VG_(strdup)("cl.bbcc.mcxt", "(no context)"); 346 347 /* Overestimate the number of bytes we need to hold the string. */ 348 SizeT need = 20; // rec_index + nul-terminator 349 for (i = 0; i < cxt->size; ++i) 350 need += VG_(strlen)(cxt->fn[i]->name) + 1; // 1 for leading ' 351 352 HChar *mangled = CLG_MALLOC("cl.bbcc.mcxt", need); 353 p = VG_(sprintf)(mangled, "%s", cxt->fn[0]->name); 354 if (rec_index >0) 355 p += VG_(sprintf)(mangled+p, "'%d", rec_index +1); 356 for(i=1;i<cxt->size;i++) 357 p += VG_(sprintf)(mangled+p, "'%s", cxt->fn[i]->name); 358 359 return mangled; 360 } 361 362 363 /* Create a new BBCC as a copy of an existing one, 364 * but with costs set to 0 and jcc chains empty. 365 * 366 * This is needed when a BB is executed in another context than 367 * the one at instrumentation time of the BB. 368 * 369 * Use cases: 370 * rec_index == 0: clone from a BBCC with differing tid/cxt 371 * and insert into hashes 372 * rec_index >0 : clone from a BBCC with same tid/cxt and rec_index 0 373 * don't insert into hashes 374 */ 375 static BBCC* clone_bbcc(BBCC* orig, Context* cxt, Int rec_index) 376 { 377 BBCC* bbcc; 378 379 CLG_DEBUG(3,"+ clone_bbcc(BB %#lx, rec %d, fn %s)\n", 380 bb_addr(orig->bb), rec_index, cxt->fn[0]->name); 381 382 bbcc = new_bbcc(orig->bb); 383 384 if (rec_index == 0) { 385 386 /* hash insertion is only allowed if tid or cxt is different */ 387 CLG_ASSERT((orig->tid != CLG_(current_tid)) || 388 (orig->cxt != cxt)); 389 390 bbcc->rec_index = 0; 391 bbcc->cxt = cxt; 392 bbcc->rec_array = new_recursion(cxt->fn[0]->separate_recursions); 393 bbcc->rec_array[0] = bbcc; 394 395 insert_bbcc_into_hash(bbcc); 396 } 397 else { 398 if (CLG_(clo).separate_threads) 399 CLG_ASSERT(orig->tid == CLG_(current_tid)); 400 401 CLG_ASSERT(orig->cxt == cxt); 402 CLG_ASSERT(orig->rec_array); 403 CLG_ASSERT(cxt->fn[0]->separate_recursions > rec_index); 404 CLG_ASSERT(orig->rec_array[rec_index] ==0); 405 406 /* new BBCC will only have differing recursion level */ 407 bbcc->rec_index = rec_index; 408 bbcc->cxt = cxt; 409 bbcc->rec_array = orig->rec_array; 410 bbcc->rec_array[rec_index] = bbcc; 411 } 412 413 /* update list of BBCCs for same BB */ 414 bbcc->next_bbcc = orig->bb->bbcc_list; 415 orig->bb->bbcc_list = bbcc; 416 417 418 CLG_DEBUGIF(3) 419 CLG_(print_bbcc)(-2, bbcc); 420 421 HChar *mangled_orig = mangled_cxt(orig->cxt, orig->rec_index); 422 HChar *mangled_bbcc = mangled_cxt(bbcc->cxt, bbcc->rec_index); 423 CLG_DEBUG(2,"- clone_BBCC(%p, %d) for BB %#lx\n" 424 " orig %s\n" 425 " new %s\n", 426 orig, rec_index, bb_addr(orig->bb), 427 mangled_orig, 428 mangled_bbcc); 429 CLG_FREE(mangled_orig); 430 CLG_FREE(mangled_bbcc); 431 432 CLG_(stat).bbcc_clones++; 433 434 return bbcc; 435 }; 436 437 438 439 /* Get a pointer to the cost centre structure for given basic block 440 * address. If created, the BBCC is inserted into the BBCC hash. 441 * Also sets BB_seen_before by reference. 442 * 443 */ 444 BBCC* CLG_(get_bbcc)(BB* bb) 445 { 446 BBCC* bbcc; 447 448 CLG_DEBUG(3, "+ get_bbcc(BB %#lx)\n", bb_addr(bb)); 449 450 bbcc = bb->bbcc_list; 451 452 if (!bbcc) { 453 bbcc = new_bbcc(bb); 454 455 /* initialize BBCC */ 456 bbcc->cxt = 0; 457 bbcc->rec_array = 0; 458 bbcc->rec_index = 0; 459 460 bbcc->next_bbcc = bb->bbcc_list; 461 bb->bbcc_list = bbcc; 462 bb->last_bbcc = bbcc; 463 464 CLG_DEBUGIF(3) 465 CLG_(print_bbcc)(-2, bbcc); 466 } 467 468 CLG_DEBUG(3, "- get_bbcc(BB %#lx): BBCC %p\n", 469 bb_addr(bb), bbcc); 470 471 return bbcc; 472 } 473 474 475 /* Callgrind manages its own call stack for each thread. 476 * When leaving a function, a underflow can happen when 477 * Callgrind's tracing was switched on in the middle of 478 * a run, i.e. when Callgrind was not able to trace the 479 * call instruction. 480 * This function tries to reconstruct the original call. 481 * As we know the return address (the address following 482 * the CALL instruction), we can detect the function 483 * we return back to, but the original call site is unknown. 484 * We suppose a call site at return address - 1. 485 * (TODO: other heuristic: lookup info of instrumented BBs). 486 */ 487 static void handleUnderflow(BB* bb) 488 { 489 /* RET at top of call stack */ 490 BBCC* source_bbcc; 491 BB* source_bb; 492 Bool seen_before; 493 fn_node* caller; 494 int fn_number; 495 unsigned *pactive; 496 call_entry* call_entry_up; 497 498 CLG_DEBUG(1," Callstack underflow !\n"); 499 500 /* we emulate an old call from the function we return to 501 * by using (<return address> -1) */ 502 source_bb = CLG_(get_bb)(bb_addr(bb)-1, 0, &seen_before); 503 source_bbcc = CLG_(get_bbcc)(source_bb); 504 505 /* seen_before can be true if RET from a signal handler */ 506 if (!seen_before) { 507 source_bbcc->ecounter_sum = CLG_(current_state).collect ? 1 : 0; 508 } 509 else if (CLG_(current_state).collect) 510 source_bbcc->ecounter_sum++; 511 512 /* Force a new top context, will be set active by push_cxt() */ 513 CLG_(current_fn_stack).top--; 514 CLG_(current_state).cxt = 0; 515 caller = CLG_(get_fn_node)(bb); 516 CLG_(push_cxt)( caller ); 517 518 if (!seen_before) { 519 /* set rec array for source BBCC: this is at rec level 1 */ 520 source_bbcc->rec_array = new_recursion(caller->separate_recursions); 521 source_bbcc->rec_array[0] = source_bbcc; 522 523 CLG_ASSERT(source_bbcc->cxt == 0); 524 source_bbcc->cxt = CLG_(current_state).cxt; 525 insert_bbcc_into_hash(source_bbcc); 526 } 527 CLG_ASSERT(CLG_(current_state).bbcc); 528 529 /* correct active counts */ 530 fn_number = CLG_(current_state).bbcc->cxt->fn[0]->number; 531 pactive = CLG_(get_fn_entry)(fn_number); 532 (*pactive)--; 533 534 /* This assertion is not correct for reentrant 535 * signal handlers */ 536 /* CLG_ASSERT(*pactive == 0); */ 537 538 CLG_(current_state).nonskipped = 0; /* we didn't skip this function */ 539 /* back to current context */ 540 CLG_(push_cxt)( CLG_(current_state).bbcc->cxt->fn[0] ); 541 CLG_(push_call_stack)(source_bbcc, 0, CLG_(current_state).bbcc, 542 (Addr)-1, False); 543 call_entry_up = 544 &(CLG_(current_call_stack).entry[CLG_(current_call_stack).sp -1]); 545 /* assume this call is lasting since last dump or 546 * for a signal handler since it's call */ 547 if (CLG_(current_state).sig == 0) 548 CLG_(copy_cost)( CLG_(sets).full, call_entry_up->enter_cost, 549 CLG_(get_current_thread)()->lastdump_cost ); 550 else 551 CLG_(zero_cost)( CLG_(sets).full, call_entry_up->enter_cost ); 552 } 553 554 555 /* 556 * Helper function called at start of each instrumented BB to setup 557 * pointer to costs for current thread/context/recursion level 558 */ 559 560 VG_REGPARM(1) 561 void CLG_(setup_bbcc)(BB* bb) 562 { 563 BBCC *bbcc, *last_bbcc; 564 Bool call_emulation = False, delayed_push = False, skip = False; 565 Addr sp; 566 BB* last_bb; 567 ThreadId tid; 568 ClgJumpKind jmpkind; 569 Bool isConditionalJump; 570 Int passed = 0, csp; 571 Bool ret_without_call = False; 572 Int popcount_on_return = 1; 573 574 CLG_DEBUG(3,"+ setup_bbcc(BB %#lx)\n", bb_addr(bb)); 575 576 /* This is needed because thread switches can not reliable be tracked 577 * with callback CLG_(run_thread) only: we have otherwise no way to get 578 * the thread ID after a signal handler returns. 579 * This could be removed again if that bug is fixed in Valgrind. 580 * This is in the hot path but hopefully not to costly. 581 */ 582 tid = VG_(get_running_tid)(); 583 #if 1 584 /* CLG_(switch_thread) is a no-op when tid is equal to CLG_(current_tid). 585 * As this is on the hot path, we only call CLG_(switch_thread)(tid) 586 * if tid differs from the CLG_(current_tid). 587 */ 588 if (UNLIKELY(tid != CLG_(current_tid))) 589 CLG_(switch_thread)(tid); 590 #else 591 CLG_ASSERT(VG_(get_running_tid)() == CLG_(current_tid)); 592 #endif 593 594 sp = VG_(get_SP)(tid); 595 last_bbcc = CLG_(current_state).bbcc; 596 last_bb = last_bbcc ? last_bbcc->bb : 0; 597 598 if (last_bb) { 599 passed = CLG_(current_state).jmps_passed; 600 CLG_ASSERT(passed <= last_bb->cjmp_count); 601 jmpkind = last_bb->jmp[passed].jmpkind; 602 isConditionalJump = (passed < last_bb->cjmp_count); 603 604 if (CLG_(current_state).collect) { 605 if (!CLG_(current_state).nonskipped) { 606 last_bbcc->ecounter_sum++; 607 last_bbcc->jmp[passed].ecounter++; 608 if (!CLG_(clo).simulate_cache) { 609 /* update Ir cost */ 610 UInt instr_count = last_bb->jmp[passed].instr+1; 611 CLG_(current_state).cost[ fullOffset(EG_IR) ] += instr_count; 612 } 613 } 614 else { 615 /* do not increment exe counter of BBs in skipped functions, as it 616 * would fool dumping code */ 617 if (!CLG_(clo).simulate_cache) { 618 /* update Ir cost */ 619 UInt instr_count = last_bb->jmp[passed].instr+1; 620 CLG_(current_state).cost[ fullOffset(EG_IR) ] += instr_count; 621 CLG_(current_state).nonskipped->skipped[ fullOffset(EG_IR) ] 622 += instr_count; 623 } 624 } 625 } 626 627 CLG_DEBUGIF(4) { 628 CLG_(print_execstate)(-2, &CLG_(current_state) ); 629 CLG_(print_bbcc_cost)(-2, last_bbcc); 630 } 631 } 632 else { 633 jmpkind = jk_None; 634 isConditionalJump = False; 635 } 636 637 /* Manipulate JmpKind if needed, only using BB specific info */ 638 639 csp = CLG_(current_call_stack).sp; 640 641 /* A return not matching the top call in our callstack is a jump */ 642 if ( (jmpkind == jk_Return) && (csp >0)) { 643 Int csp_up = csp-1; 644 call_entry* top_ce = &(CLG_(current_call_stack).entry[csp_up]); 645 646 /* We have a real return if 647 * - the stack pointer (SP) left the current stack frame, or 648 * - SP has the same value as when reaching the current function 649 * and the address of this BB is the return address of last call 650 * (we even allow to leave multiple frames if the SP stays the 651 * same and we find a matching return address) 652 * The latter condition is needed because on PPC, SP can stay 653 * the same over CALL=b(c)l / RET=b(c)lr boundaries 654 */ 655 if (sp < top_ce->sp) popcount_on_return = 0; 656 else if (top_ce->sp == sp) { 657 while(1) { 658 if (top_ce->ret_addr == bb_addr(bb)) break; 659 if (csp_up>0) { 660 csp_up--; 661 top_ce = &(CLG_(current_call_stack).entry[csp_up]); 662 if (top_ce->sp == sp) { 663 popcount_on_return++; 664 continue; 665 } 666 } 667 popcount_on_return = 0; 668 break; 669 } 670 } 671 if (popcount_on_return == 0) { 672 jmpkind = jk_Jump; 673 ret_without_call = True; 674 } 675 } 676 677 /* Should this jump be converted to call or pop/call ? */ 678 if (( jmpkind != jk_Return) && 679 ( jmpkind != jk_Call) && last_bb) { 680 681 /* We simulate a JMP/Cont to be a CALL if 682 * - jump is in another ELF object or section kind 683 * - jump is to first instruction of a function (tail recursion) 684 */ 685 if (ret_without_call || 686 /* This is for detection of optimized tail recursion. 687 * On PPC, this is only detected as call when going to another 688 * function. The problem is that on PPC it can go wrong 689 * more easily (no stack frame setup needed) 690 */ 691 #if defined(VGA_ppc32) 692 (bb->is_entry && (last_bb->fn != bb->fn)) || 693 #else 694 bb->is_entry || 695 #endif 696 (last_bb->sect_kind != bb->sect_kind) || 697 (last_bb->obj->number != bb->obj->number)) { 698 699 CLG_DEBUG(1," JMP: %s[%s] to %s[%s]%s!\n", 700 last_bb->fn->name, last_bb->obj->name, 701 bb->fn->name, bb->obj->name, 702 ret_without_call?" (RET w/o CALL)":""); 703 704 if (CLG_(get_fn_node)(last_bb)->pop_on_jump && (csp>0)) { 705 706 call_entry* top_ce = &(CLG_(current_call_stack).entry[csp-1]); 707 708 if (top_ce->jcc) { 709 710 CLG_DEBUG(1," Pop on Jump!\n"); 711 712 /* change source for delayed push */ 713 CLG_(current_state).bbcc = top_ce->jcc->from; 714 sp = top_ce->sp; 715 passed = top_ce->jcc->jmp; 716 CLG_(pop_call_stack)(); 717 } 718 else { 719 CLG_ASSERT(CLG_(current_state).nonskipped != 0); 720 } 721 } 722 723 jmpkind = jk_Call; 724 call_emulation = True; 725 } 726 } 727 728 if (jmpkind == jk_Call) 729 skip = CLG_(get_fn_node)(bb)->skip; 730 731 CLG_DEBUGIF(1) { 732 if (isConditionalJump) 733 VG_(printf)("Cond-"); 734 switch(jmpkind) { 735 case jk_None: VG_(printf)("Fall-through"); break; 736 case jk_Jump: VG_(printf)("Jump"); break; 737 case jk_Call: VG_(printf)("Call"); break; 738 case jk_Return: VG_(printf)("Return"); break; 739 default: tl_assert(0); 740 } 741 VG_(printf)(" %08lx -> %08lx, SP %08lx\n", 742 last_bb ? bb_jmpaddr(last_bb) : 0, 743 bb_addr(bb), sp); 744 } 745 746 /* Handle CALL/RET and update context to get correct BBCC */ 747 748 if (jmpkind == jk_Return) { 749 750 if ((csp == 0) || 751 ((CLG_(current_fn_stack).top > CLG_(current_fn_stack).bottom) && 752 ( *(CLG_(current_fn_stack).top-1)==0)) ) { 753 754 /* On an empty call stack or at a signal separation marker, 755 * a RETURN generates an call stack underflow. 756 */ 757 handleUnderflow(bb); 758 CLG_(pop_call_stack)(); 759 } 760 else { 761 CLG_ASSERT(popcount_on_return >0); 762 CLG_(unwind_call_stack)(sp, popcount_on_return); 763 } 764 } 765 else { 766 Int unwind_count = CLG_(unwind_call_stack)(sp, 0); 767 if (unwind_count > 0) { 768 /* if unwinding was done, this actually is a return */ 769 jmpkind = jk_Return; 770 } 771 772 if (jmpkind == jk_Call) { 773 delayed_push = True; 774 775 csp = CLG_(current_call_stack).sp; 776 if (call_emulation && csp>0) 777 sp = CLG_(current_call_stack).entry[csp-1].sp; 778 779 } 780 } 781 782 /* Change new context if needed, taking delayed_push into account */ 783 if ((delayed_push && !skip) || (CLG_(current_state).cxt == 0)) { 784 CLG_(push_cxt)(CLG_(get_fn_node)(bb)); 785 } 786 CLG_ASSERT(CLG_(current_fn_stack).top > CLG_(current_fn_stack).bottom); 787 788 /* If there is a fresh instrumented BBCC, assign current context */ 789 bbcc = CLG_(get_bbcc)(bb); 790 if (bbcc->cxt == 0) { 791 CLG_ASSERT(bbcc->rec_array == 0); 792 793 bbcc->cxt = CLG_(current_state).cxt; 794 bbcc->rec_array = 795 new_recursion((*CLG_(current_fn_stack).top)->separate_recursions); 796 bbcc->rec_array[0] = bbcc; 797 798 insert_bbcc_into_hash(bbcc); 799 } 800 else { 801 /* get BBCC with current context */ 802 803 /* first check LRU of last bbcc executed */ 804 805 if (last_bbcc) { 806 bbcc = last_bbcc->lru_next_bbcc; 807 if (bbcc && 808 ((bbcc->bb != bb) || 809 (bbcc->cxt != CLG_(current_state).cxt))) 810 bbcc = 0; 811 } 812 else 813 bbcc = 0; 814 815 if (!bbcc) 816 bbcc = lookup_bbcc(bb, CLG_(current_state).cxt); 817 if (!bbcc) 818 bbcc = clone_bbcc(bb->bbcc_list, CLG_(current_state).cxt, 0); 819 820 bb->last_bbcc = bbcc; 821 } 822 823 /* save for fast lookup */ 824 if (last_bbcc) 825 last_bbcc->lru_next_bbcc = bbcc; 826 827 if ((*CLG_(current_fn_stack).top)->separate_recursions >1) { 828 UInt level, idx; 829 fn_node* top = *(CLG_(current_fn_stack).top); 830 831 level = *CLG_(get_fn_entry)(top->number); 832 833 if (delayed_push && !skip) { 834 if (CLG_(clo).skip_direct_recursion) { 835 /* a call was detected, which means that the source BB != 0 */ 836 CLG_ASSERT(CLG_(current_state).bbcc != 0); 837 /* only increment rec. level if called from different function */ 838 if (CLG_(current_state).bbcc->cxt->fn[0] != bbcc->cxt->fn[0]) 839 level++; 840 } 841 else level++; 842 } 843 if (level> top->separate_recursions) 844 level = top->separate_recursions; 845 846 if (level == 0) { 847 /* can only happen if instrumentation just was switched on */ 848 level = 1; 849 *CLG_(get_fn_entry)(top->number) = 1; 850 } 851 852 idx = level -1; 853 if (bbcc->rec_array[idx]) 854 bbcc = bbcc->rec_array[idx]; 855 else 856 bbcc = clone_bbcc(bbcc, CLG_(current_state).cxt, idx); 857 858 CLG_ASSERT(bbcc->rec_array[bbcc->rec_index] == bbcc); 859 } 860 861 if (delayed_push) { 862 if (!skip && CLG_(current_state).nonskipped) { 863 /* a call from skipped to nonskipped */ 864 CLG_(current_state).bbcc = CLG_(current_state).nonskipped; 865 /* FIXME: take the real passed count from shadow stack */ 866 passed = CLG_(current_state).bbcc->bb->cjmp_count; 867 } 868 CLG_(push_call_stack)(CLG_(current_state).bbcc, passed, 869 bbcc, sp, skip); 870 } 871 872 if (CLG_(clo).collect_jumps && (jmpkind == jk_Jump)) { 873 874 /* Handle conditional jumps followed, i.e. trace arcs 875 * This uses JCC structures, too */ 876 877 jCC* jcc = CLG_(get_jcc)(last_bbcc, passed, bbcc); 878 CLG_ASSERT(jcc != 0); 879 // Change from default, and check if already changed 880 if (jcc->jmpkind == jk_Call) 881 jcc->jmpkind = isConditionalJump ? jk_CondJump : jk_Jump; 882 else { 883 // FIXME: Why can this fail? 884 // CLG_ASSERT(jcc->jmpkind == jmpkind); 885 } 886 887 jcc->call_counter++; 888 if (isConditionalJump) 889 CLG_(stat).jcnd_counter++; 890 else 891 CLG_(stat).jump_counter++; 892 } 893 894 CLG_(current_state).bbcc = bbcc; 895 /* Even though this will be set in instrumented code directly before 896 * side exits, it needs to be set to 0 here in case an exception 897 * happens in first instructions of the BB */ 898 CLG_(current_state).jmps_passed = 0; 899 // needed for log_* handlers called in this BB 900 CLG_(bb_base) = bb->obj->offset + bb->offset; 901 CLG_(cost_base) = bbcc->cost; 902 903 CLG_DEBUGIF(1) { 904 VG_(printf)(" "); 905 CLG_(print_bbcc_fn)(bbcc); 906 VG_(printf)("\n"); 907 } 908 909 CLG_DEBUG(3,"- setup_bbcc (BB %#lx): Cost %p (Len %u), Instrs %u (Len %u)\n", 910 bb_addr(bb), bbcc->cost, bb->cost_count, 911 bb->instr_count, bb->instr_len); 912 CLG_DEBUGIF(3) 913 CLG_(print_cxt)(-8, CLG_(current_state).cxt, bbcc->rec_index); 914 CLG_DEBUG(3,"\n"); 915 916 CLG_(stat).bb_executions++; 917 } 918
