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