1 /* Prologue value handling for GDB. 2 Copyright 2003, 2004, 2005, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 5 This file is part of GDB. 6 7 This program is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 19 20 #include "defs.h" 21 #include "gdb_string.h" 22 #include "gdb_assert.h" 23 #include "prologue-value.h" 24 #include "regcache.h" 25 26 27 /* Constructors. */ 28 29 pv_t 30 pv_unknown (void) 31 { 32 pv_t v = { pvk_unknown, 0, 0 }; 33 34 return v; 35 } 36 37 38 pv_t 39 pv_constant (CORE_ADDR k) 40 { 41 pv_t v; 42 43 v.kind = pvk_constant; 44 v.reg = -1; /* for debugging */ 45 v.k = k; 46 47 return v; 48 } 49 50 51 pv_t 52 pv_register (int reg, CORE_ADDR k) 53 { 54 pv_t v; 55 56 v.kind = pvk_register; 57 v.reg = reg; 58 v.k = k; 59 60 return v; 61 } 62 63 64 65 /* Arithmetic operations. */ 66 67 /* If one of *A and *B is a constant, and the other isn't, swap the 68 values as necessary to ensure that *B is the constant. This can 69 reduce the number of cases we need to analyze in the functions 70 below. */ 71 static void 72 constant_last (pv_t *a, pv_t *b) 73 { 74 if (a->kind == pvk_constant 75 && b->kind != pvk_constant) 76 { 77 pv_t temp = *a; 78 *a = *b; 79 *b = temp; 80 } 81 } 82 83 84 pv_t 85 pv_add (pv_t a, pv_t b) 86 { 87 constant_last (&a, &b); 88 89 /* We can add a constant to a register. */ 90 if (a.kind == pvk_register 91 && b.kind == pvk_constant) 92 return pv_register (a.reg, a.k + b.k); 93 94 /* We can add a constant to another constant. */ 95 else if (a.kind == pvk_constant 96 && b.kind == pvk_constant) 97 return pv_constant (a.k + b.k); 98 99 /* Anything else we don't know how to add. We don't have a 100 representation for, say, the sum of two registers, or a multiple 101 of a register's value (adding a register to itself). */ 102 else 103 return pv_unknown (); 104 } 105 106 107 pv_t 108 pv_add_constant (pv_t v, CORE_ADDR k) 109 { 110 /* Rather than thinking of all the cases we can and can't handle, 111 we'll just let pv_add take care of that for us. */ 112 return pv_add (v, pv_constant (k)); 113 } 114 115 116 pv_t 117 pv_subtract (pv_t a, pv_t b) 118 { 119 /* This isn't quite the same as negating B and adding it to A, since 120 we don't have a representation for the negation of anything but a 121 constant. For example, we can't negate { pvk_register, R1, 10 }, 122 but we do know that { pvk_register, R1, 10 } minus { pvk_register, 123 R1, 5 } is { pvk_constant, <ignored>, 5 }. 124 125 This means, for example, that we could subtract two stack 126 addresses; they're both relative to the original SP. Since the 127 frame pointer is set based on the SP, its value will be the 128 original SP plus some constant (probably zero), so we can use its 129 value just fine, too. */ 130 131 constant_last (&a, &b); 132 133 /* We can subtract two constants. */ 134 if (a.kind == pvk_constant 135 && b.kind == pvk_constant) 136 return pv_constant (a.k - b.k); 137 138 /* We can subtract a constant from a register. */ 139 else if (a.kind == pvk_register 140 && b.kind == pvk_constant) 141 return pv_register (a.reg, a.k - b.k); 142 143 /* We can subtract a register from itself, yielding a constant. */ 144 else if (a.kind == pvk_register 145 && b.kind == pvk_register 146 && a.reg == b.reg) 147 return pv_constant (a.k - b.k); 148 149 /* We don't know how to subtract anything else. */ 150 else 151 return pv_unknown (); 152 } 153 154 155 pv_t 156 pv_logical_and (pv_t a, pv_t b) 157 { 158 constant_last (&a, &b); 159 160 /* We can 'and' two constants. */ 161 if (a.kind == pvk_constant 162 && b.kind == pvk_constant) 163 return pv_constant (a.k & b.k); 164 165 /* We can 'and' anything with the constant zero. */ 166 else if (b.kind == pvk_constant 167 && b.k == 0) 168 return pv_constant (0); 169 170 /* We can 'and' anything with ~0. */ 171 else if (b.kind == pvk_constant 172 && b.k == ~ (CORE_ADDR) 0) 173 return a; 174 175 /* We can 'and' a register with itself. */ 176 else if (a.kind == pvk_register 177 && b.kind == pvk_register 178 && a.reg == b.reg 179 && a.k == b.k) 180 return a; 181 182 /* Otherwise, we don't know. */ 183 else 184 return pv_unknown (); 185 } 186 187 188 189 /* Examining prologue values. */ 190 191 int 192 pv_is_identical (pv_t a, pv_t b) 193 { 194 if (a.kind != b.kind) 195 return 0; 196 197 switch (a.kind) 198 { 199 case pvk_unknown: 200 return 1; 201 case pvk_constant: 202 return (a.k == b.k); 203 case pvk_register: 204 return (a.reg == b.reg && a.k == b.k); 205 default: 206 gdb_assert (0); 207 } 208 } 209 210 211 int 212 pv_is_constant (pv_t a) 213 { 214 return (a.kind == pvk_constant); 215 } 216 217 218 int 219 pv_is_register (pv_t a, int r) 220 { 221 return (a.kind == pvk_register 222 && a.reg == r); 223 } 224 225 226 int 227 pv_is_register_k (pv_t a, int r, CORE_ADDR k) 228 { 229 return (a.kind == pvk_register 230 && a.reg == r 231 && a.k == k); 232 } 233 234 235 enum pv_boolean 236 pv_is_array_ref (pv_t addr, CORE_ADDR size, 237 pv_t array_addr, CORE_ADDR array_len, 238 CORE_ADDR elt_size, 239 int *i) 240 { 241 /* Note that, since .k is a CORE_ADDR, and CORE_ADDR is unsigned, if 242 addr is *before* the start of the array, then this isn't going to 243 be negative... */ 244 pv_t offset = pv_subtract (addr, array_addr); 245 246 if (offset.kind == pvk_constant) 247 { 248 /* This is a rather odd test. We want to know if the SIZE bytes 249 at ADDR don't overlap the array at all, so you'd expect it to 250 be an || expression: "if we're completely before || we're 251 completely after". But with unsigned arithmetic, things are 252 different: since it's a number circle, not a number line, the 253 right values for offset.k are actually one contiguous range. */ 254 if (offset.k <= -size 255 && offset.k >= array_len * elt_size) 256 return pv_definite_no; 257 else if (offset.k % elt_size != 0 258 || size != elt_size) 259 return pv_maybe; 260 else 261 { 262 *i = offset.k / elt_size; 263 return pv_definite_yes; 264 } 265 } 266 else 267 return pv_maybe; 268 } 269 270 271 272 /* Areas. */ 273 274 275 /* A particular value known to be stored in an area. 276 277 Entries form a ring, sorted by unsigned offset from the area's base 278 register's value. Since entries can straddle the wrap-around point, 279 unsigned offsets form a circle, not a number line, so the list 280 itself is structured the same way --- there is no inherent head. 281 The entry with the lowest offset simply follows the entry with the 282 highest offset. Entries may abut, but never overlap. The area's 283 'entry' pointer points to an arbitrary node in the ring. */ 284 struct area_entry 285 { 286 /* Links in the doubly-linked ring. */ 287 struct area_entry *prev, *next; 288 289 /* Offset of this entry's address from the value of the base 290 register. */ 291 CORE_ADDR offset; 292 293 /* The size of this entry. Note that an entry may wrap around from 294 the end of the address space to the beginning. */ 295 CORE_ADDR size; 296 297 /* The value stored here. */ 298 pv_t value; 299 }; 300 301 302 struct pv_area 303 { 304 /* This area's base register. */ 305 int base_reg; 306 307 /* The mask to apply to addresses, to make the wrap-around happen at 308 the right place. */ 309 CORE_ADDR addr_mask; 310 311 /* An element of the doubly-linked ring of entries, or zero if we 312 have none. */ 313 struct area_entry *entry; 314 }; 315 316 317 struct pv_area * 318 make_pv_area (int base_reg, int addr_bit) 319 { 320 struct pv_area *a = (struct pv_area *) xmalloc (sizeof (*a)); 321 322 memset (a, 0, sizeof (*a)); 323 324 a->base_reg = base_reg; 325 a->entry = 0; 326 327 /* Remember that shift amounts equal to the type's width are 328 undefined. */ 329 a->addr_mask = ((((CORE_ADDR) 1 << (addr_bit - 1)) - 1) << 1) | 1; 330 331 return a; 332 } 333 334 335 /* Delete all entries from AREA. */ 336 static void 337 clear_entries (struct pv_area *area) 338 { 339 struct area_entry *e = area->entry; 340 341 if (e) 342 { 343 /* This needs to be a do-while loop, in order to actually 344 process the node being checked for in the terminating 345 condition. */ 346 do 347 { 348 struct area_entry *next = e->next; 349 350 xfree (e); 351 e = next; 352 } 353 while (e != area->entry); 354 355 area->entry = 0; 356 } 357 } 358 359 360 void 361 free_pv_area (struct pv_area *area) 362 { 363 clear_entries (area); 364 xfree (area); 365 } 366 367 368 static void 369 do_free_pv_area_cleanup (void *arg) 370 { 371 free_pv_area ((struct pv_area *) arg); 372 } 373 374 375 struct cleanup * 376 make_cleanup_free_pv_area (struct pv_area *area) 377 { 378 return make_cleanup (do_free_pv_area_cleanup, (void *) area); 379 } 380 381 382 int 383 pv_area_store_would_trash (struct pv_area *area, pv_t addr) 384 { 385 /* It may seem odd that pvk_constant appears here --- after all, 386 that's the case where we know the most about the address! But 387 pv_areas are always relative to a register, and we don't know the 388 value of the register, so we can't compare entry addresses to 389 constants. */ 390 return (addr.kind == pvk_unknown 391 || addr.kind == pvk_constant 392 || (addr.kind == pvk_register && addr.reg != area->base_reg)); 393 } 394 395 396 /* Return a pointer to the first entry we hit in AREA starting at 397 OFFSET and going forward. 398 399 This may return zero, if AREA has no entries. 400 401 And since the entries are a ring, this may return an entry that 402 entirely preceeds OFFSET. This is the correct behavior: depending 403 on the sizes involved, we could still overlap such an area, with 404 wrap-around. */ 405 static struct area_entry * 406 find_entry (struct pv_area *area, CORE_ADDR offset) 407 { 408 struct area_entry *e = area->entry; 409 410 if (! e) 411 return 0; 412 413 /* If the next entry would be better than the current one, then scan 414 forward. Since we use '<' in this loop, it always terminates. 415 416 Note that, even setting aside the addr_mask stuff, we must not 417 simplify this, in high school algebra fashion, to 418 (e->next->offset < e->offset), because of the way < interacts 419 with wrap-around. We have to subtract offset from both sides to 420 make sure both things we're comparing are on the same side of the 421 discontinuity. */ 422 while (((e->next->offset - offset) & area->addr_mask) 423 < ((e->offset - offset) & area->addr_mask)) 424 e = e->next; 425 426 /* If the previous entry would be better than the current one, then 427 scan backwards. */ 428 while (((e->prev->offset - offset) & area->addr_mask) 429 < ((e->offset - offset) & area->addr_mask)) 430 e = e->prev; 431 432 /* In case there's some locality to the searches, set the area's 433 pointer to the entry we've found. */ 434 area->entry = e; 435 436 return e; 437 } 438 439 440 /* Return non-zero if the SIZE bytes at OFFSET would overlap ENTRY; 441 return zero otherwise. AREA is the area to which ENTRY belongs. */ 442 static int 443 overlaps (struct pv_area *area, 444 struct area_entry *entry, 445 CORE_ADDR offset, 446 CORE_ADDR size) 447 { 448 /* Think carefully about wrap-around before simplifying this. */ 449 return (((entry->offset - offset) & area->addr_mask) < size 450 || ((offset - entry->offset) & area->addr_mask) < entry->size); 451 } 452 453 454 void 455 pv_area_store (struct pv_area *area, 456 pv_t addr, 457 CORE_ADDR size, 458 pv_t value) 459 { 460 /* Remove any (potentially) overlapping entries. */ 461 if (pv_area_store_would_trash (area, addr)) 462 clear_entries (area); 463 else 464 { 465 CORE_ADDR offset = addr.k; 466 struct area_entry *e = find_entry (area, offset); 467 468 /* Delete all entries that we would overlap. */ 469 while (e && overlaps (area, e, offset, size)) 470 { 471 struct area_entry *next = (e->next == e) ? 0 : e->next; 472 473 e->prev->next = e->next; 474 e->next->prev = e->prev; 475 476 xfree (e); 477 e = next; 478 } 479 480 /* Move the area's pointer to the next remaining entry. This 481 will also zero the pointer if we've deleted all the entries. */ 482 area->entry = e; 483 } 484 485 /* Now, there are no entries overlapping us, and area->entry is 486 either zero or pointing at the closest entry after us. We can 487 just insert ourselves before that. 488 489 But if we're storing an unknown value, don't bother --- that's 490 the default. */ 491 if (value.kind == pvk_unknown) 492 return; 493 else 494 { 495 CORE_ADDR offset = addr.k; 496 struct area_entry *e = (struct area_entry *) xmalloc (sizeof (*e)); 497 498 e->offset = offset; 499 e->size = size; 500 e->value = value; 501 502 if (area->entry) 503 { 504 e->prev = area->entry->prev; 505 e->next = area->entry; 506 e->prev->next = e->next->prev = e; 507 } 508 else 509 { 510 e->prev = e->next = e; 511 area->entry = e; 512 } 513 } 514 } 515 516 517 pv_t 518 pv_area_fetch (struct pv_area *area, pv_t addr, CORE_ADDR size) 519 { 520 /* If we have no entries, or we can't decide how ADDR relates to the 521 entries we do have, then the value is unknown. */ 522 if (! area->entry 523 || pv_area_store_would_trash (area, addr)) 524 return pv_unknown (); 525 else 526 { 527 CORE_ADDR offset = addr.k; 528 struct area_entry *e = find_entry (area, offset); 529 530 /* If this entry exactly matches what we're looking for, then 531 we're set. Otherwise, say it's unknown. */ 532 if (e->offset == offset && e->size == size) 533 return e->value; 534 else 535 return pv_unknown (); 536 } 537 } 538 539 540 int 541 pv_area_find_reg (struct pv_area *area, 542 struct gdbarch *gdbarch, 543 int reg, 544 CORE_ADDR *offset_p) 545 { 546 struct area_entry *e = area->entry; 547 548 if (e) 549 do 550 { 551 if (e->value.kind == pvk_register 552 && e->value.reg == reg 553 && e->value.k == 0 554 && e->size == register_size (gdbarch, reg)) 555 { 556 if (offset_p) 557 *offset_p = e->offset; 558 return 1; 559 } 560 561 e = e->next; 562 } 563 while (e != area->entry); 564 565 return 0; 566 } 567 568 569 void 570 pv_area_scan (struct pv_area *area, 571 void (*func) (void *closure, 572 pv_t addr, 573 CORE_ADDR size, 574 pv_t value), 575 void *closure) 576 { 577 struct area_entry *e = area->entry; 578 pv_t addr; 579 580 addr.kind = pvk_register; 581 addr.reg = area->base_reg; 582 583 if (e) 584 do 585 { 586 addr.k = e->offset; 587 func (closure, addr, e->size, e->value); 588 e = e->next; 589 } 590 while (e != area->entry); 591 } 592