gdb/prologue-value.c

   1 /* Prologue value handling for GDB.
   2    Copyright 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
   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 \f
  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 \f
  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 \f
 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_not_reached ("unexpected prologue value kind");
 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 \f
 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 precedes 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 }