gdb/prologue-value.c

   1 /* Prologue value handling for GDB.
   2    Copyright (C) 2003-2014 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 <string.h>
  21 #include "gdb_assert.h"
  22 #include "prologue-value.h"
  23 #include "regcache.h"
  24
  25 \f
  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 \f
  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 \f
 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_not_reached ("unexpected prologue value kind");
 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 \f
 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
 349           xfree (e);
 350           e = next;
 351         }
 352       while (e != area->entry);
 353
 354       area->entry = 0;
 355     }
 356 }
 357
 358
 359 void
 360 free_pv_area (struct pv_area *area)
 361 {
 362   clear_entries (area);
 363   xfree (area);
 364 }
 365
 366
 367 static void
 368 do_free_pv_area_cleanup (void *arg)
 369 {
 370   free_pv_area ((struct pv_area *) arg);
 371 }
 372
 373
 374 struct cleanup *
 375 make_cleanup_free_pv_area (struct pv_area *area)
 376 {
 377   return make_cleanup (do_free_pv_area_cleanup, (void *) area);
 378 }
 379
 380
 381 int
 382 pv_area_store_would_trash (struct pv_area *area, pv_t addr)
 383 {
 384   /* It may seem odd that pvk_constant appears here --- after all,
 385      that's the case where we know the most about the address!  But
 386      pv_areas are always relative to a register, and we don't know the
 387      value of the register, so we can't compare entry addresses to
 388      constants.  */
 389   return (addr.kind == pvk_unknown
 390           || addr.kind == pvk_constant
 391           || (addr.kind == pvk_register && addr.reg != area->base_reg));
 392 }
 393
 394
 395 /* Return a pointer to the first entry we hit in AREA starting at
 396    OFFSET and going forward.
 397
 398    This may return zero, if AREA has no entries.
 399
 400    And since the entries are a ring, this may return an entry that
 401    entirely precedes OFFSET.  This is the correct behavior: depending
 402    on the sizes involved, we could still overlap such an area, with
 403    wrap-around.  */
 404 static struct area_entry *
 405 find_entry (struct pv_area *area, CORE_ADDR offset)
 406 {
 407   struct area_entry *e = area->entry;
 408
 409   if (! e)
 410     return 0;
 411
 412   /* If the next entry would be better than the current one, then scan
 413      forward.  Since we use '<' in this loop, it always terminates.
 414
 415      Note that, even setting aside the addr_mask stuff, we must not
 416      simplify this, in high school algebra fashion, to
 417      (e->next->offset < e->offset), because of the way < interacts
 418      with wrap-around.  We have to subtract offset from both sides to
 419      make sure both things we're comparing are on the same side of the
 420      discontinuity.  */
 421   while (((e->next->offset - offset) & area->addr_mask)
 422          < ((e->offset - offset) & area->addr_mask))
 423     e = e->next;
 424
 425   /* If the previous entry would be better than the current one, then
 426      scan backwards.  */
 427   while (((e->prev->offset - offset) & area->addr_mask)
 428          < ((e->offset - offset) & area->addr_mask))
 429     e = e->prev;
 430
 431   /* In case there's some locality to the searches, set the area's
 432      pointer to the entry we've found.  */
 433   area->entry = e;
 434
 435   return e;
 436 }
 437
 438
 439 /* Return non-zero if the SIZE bytes at OFFSET would overlap ENTRY;
 440    return zero otherwise.  AREA is the area to which ENTRY belongs.  */
 441 static int
 442 overlaps (struct pv_area *area,
 443           struct area_entry *entry,
 444           CORE_ADDR offset,
 445           CORE_ADDR size)
 446 {
 447   /* Think carefully about wrap-around before simplifying this.  */
 448   return (((entry->offset - offset) & area->addr_mask) < size
 449           || ((offset - entry->offset) & area->addr_mask) < entry->size);
 450 }
 451
 452
 453 void
 454 pv_area_store (struct pv_area *area,
 455                pv_t addr,
 456                CORE_ADDR size,
 457                pv_t value)
 458 {
 459   /* Remove any (potentially) overlapping entries.  */
 460   if (pv_area_store_would_trash (area, addr))
 461     clear_entries (area);
 462   else
 463     {
 464       CORE_ADDR offset = addr.k;
 465       struct area_entry *e = find_entry (area, offset);
 466
 467       /* Delete all entries that we would overlap.  */
 468       while (e && overlaps (area, e, offset, size))
 469         {
 470           struct area_entry *next = (e->next == e) ? 0 : e->next;
 471
 472           e->prev->next = e->next;
 473           e->next->prev = e->prev;
 474
 475           xfree (e);
 476           e = next;
 477         }
 478
 479       /* Move the area's pointer to the next remaining entry.  This
 480          will also zero the pointer if we've deleted all the entries.  */
 481       area->entry = e;
 482     }
 483
 484   /* Now, there are no entries overlapping us, and area->entry is
 485      either zero or pointing at the closest entry after us.  We can
 486      just insert ourselves before that.
 487
 488      But if we're storing an unknown value, don't bother --- that's
 489      the default.  */
 490   if (value.kind == pvk_unknown)
 491     return;
 492   else
 493     {
 494       CORE_ADDR offset = addr.k;
 495       struct area_entry *e = (struct area_entry *) xmalloc (sizeof (*e));
 496
 497       e->offset = offset;
 498       e->size = size;
 499       e->value = value;
 500
 501       if (area->entry)
 502         {
 503           e->prev = area->entry->prev;
 504           e->next = area->entry;
 505           e->prev->next = e->next->prev = e;
 506         }
 507       else
 508         {
 509           e->prev = e->next = e;
 510           area->entry = e;
 511         }
 512     }
 513 }
 514
 515
 516 pv_t
 517 pv_area_fetch (struct pv_area *area, pv_t addr, CORE_ADDR size)
 518 {
 519   /* If we have no entries, or we can't decide how ADDR relates to the
 520      entries we do have, then the value is unknown.  */
 521   if (! area->entry
 522       || pv_area_store_would_trash (area, addr))
 523     return pv_unknown ();
 524   else
 525     {
 526       CORE_ADDR offset = addr.k;
 527       struct area_entry *e = find_entry (area, offset);
 528
 529       /* If this entry exactly matches what we're looking for, then
 530          we're set.  Otherwise, say it's unknown.  */
 531       if (e->offset == offset && e->size == size)
 532         return e->value;
 533       else
 534         return pv_unknown ();
 535     }
 536 }
 537
 538
 539 int
 540 pv_area_find_reg (struct pv_area *area,
 541                   struct gdbarch *gdbarch,
 542                   int reg,
 543                   CORE_ADDR *offset_p)
 544 {
 545   struct area_entry *e = area->entry;
 546
 547   if (e)
 548     do
 549       {
 550         if (e->value.kind == pvk_register
 551             && e->value.reg == reg
 552             && e->value.k == 0
 553             && e->size == register_size (gdbarch, reg))
 554           {
 555             if (offset_p)
 556               *offset_p = e->offset;
 557             return 1;
 558           }
 559
 560         e = e->next;
 561       }
 562     while (e != area->entry);
 563
 564   return 0;
 565 }
 566
 567
 568 void
 569 pv_area_scan (struct pv_area *area,
 570               void (*func) (void *closure,
 571                             pv_t addr,
 572                             CORE_ADDR size,
 573                             pv_t value),
 574               void *closure)
 575 {
 576   struct area_entry *e = area->entry;
 577   pv_t addr;
 578
 579   addr.kind = pvk_register;
 580   addr.reg = area->base_reg;
 581
 582   if (e)
 583     do
 584       {
 585         addr.k = e->offset;
 586         func (closure, addr, e->size, e->value);
 587         e = e->next;
 588       }
 589     while (e != area->entry);
 590 }