gdb/prologue-value.c

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