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