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 "prologue-value.h"
  22 #include "regcache.h"
  23
  24 \f
  25 /* Constructors.  */
  26
  27 pv_t
  28 pv_unknown (void)
  29 {
  30   pv_t v = { pvk_unknown, 0, 0 };
  31
  32   return v;
  33 }
  34
  35
  36 pv_t
  37 pv_constant (CORE_ADDR k)
  38 {
  39   pv_t v;
  40
  41   v.kind = pvk_constant;
  42   v.reg = -1;                   /* for debugging */
  43   v.k = k;
  44
  45   return v;
  46 }
  47
  48
  49 pv_t
  50 pv_register (int reg, CORE_ADDR k)
  51 {
  52   pv_t v;
  53
  54   v.kind = pvk_register;
  55   v.reg = reg;
  56   v.k = k;
  57
  58   return v;
  59 }
  60
  61
  62 \f
  63 /* Arithmetic operations.  */
  64
  65 /* If one of *A and *B is a constant, and the other isn't, swap the
  66    values as necessary to ensure that *B is the constant.  This can
  67    reduce the number of cases we need to analyze in the functions
  68    below.  */
  69 static void
  70 constant_last (pv_t *a, pv_t *b)
  71 {
  72   if (a->kind == pvk_constant
  73       && b->kind != pvk_constant)
  74     {
  75       pv_t temp = *a;
  76       *a = *b;
  77       *b = temp;
  78     }
  79 }
  80
  81
  82 pv_t
  83 pv_add (pv_t a, pv_t b)
  84 {
  85   constant_last (&a, &b);
  86
  87   /* We can add a constant to a register.  */
  88   if (a.kind == pvk_register
  89       && b.kind == pvk_constant)
  90     return pv_register (a.reg, a.k + b.k);
  91
  92   /* We can add a constant to another constant.  */
  93   else if (a.kind == pvk_constant
  94            && b.kind == pvk_constant)
  95     return pv_constant (a.k + b.k);
  96
  97   /* Anything else we don't know how to add.  We don't have a
  98      representation for, say, the sum of two registers, or a multiple
  99      of a register's value (adding a register to itself).  */
 100   else
 101     return pv_unknown ();
 102 }
 103
 104
 105 pv_t
 106 pv_add_constant (pv_t v, CORE_ADDR k)
 107 {
 108   /* Rather than thinking of all the cases we can and can't handle,
 109      we'll just let pv_add take care of that for us.  */
 110   return pv_add (v, pv_constant (k));
 111 }
 112
 113
 114 pv_t
 115 pv_subtract (pv_t a, pv_t b)
 116 {
 117   /* This isn't quite the same as negating B and adding it to A, since
 118      we don't have a representation for the negation of anything but a
 119      constant.  For example, we can't negate { pvk_register, R1, 10 },
 120      but we do know that { pvk_register, R1, 10 } minus { pvk_register,
 121      R1, 5 } is { pvk_constant, <ignored>, 5 }.
 122
 123      This means, for example, that we could subtract two stack
 124      addresses; they're both relative to the original SP.  Since the
 125      frame pointer is set based on the SP, its value will be the
 126      original SP plus some constant (probably zero), so we can use its
 127      value just fine, too.  */
 128
 129   constant_last (&a, &b);
 130
 131   /* We can subtract two constants.  */
 132   if (a.kind == pvk_constant
 133       && b.kind == pvk_constant)
 134     return pv_constant (a.k - b.k);
 135
 136   /* We can subtract a constant from a register.  */
 137   else if (a.kind == pvk_register
 138            && b.kind == pvk_constant)
 139     return pv_register (a.reg, a.k - b.k);
 140
 141   /* We can subtract a register from itself, yielding a constant.  */
 142   else if (a.kind == pvk_register
 143            && b.kind == pvk_register
 144            && a.reg == b.reg)
 145     return pv_constant (a.k - b.k);
 146
 147   /* We don't know how to subtract anything else.  */
 148   else
 149     return pv_unknown ();
 150 }
 151
 152
 153 pv_t
 154 pv_logical_and (pv_t a, pv_t b)
 155 {
 156   constant_last (&a, &b);
 157
 158   /* We can 'and' two constants.  */
 159   if (a.kind == pvk_constant
 160       && b.kind == pvk_constant)
 161     return pv_constant (a.k & b.k);
 162
 163   /* We can 'and' anything with the constant zero.  */
 164   else if (b.kind == pvk_constant
 165            && b.k == 0)
 166     return pv_constant (0);
 167
 168   /* We can 'and' anything with ~0.  */
 169   else if (b.kind == pvk_constant
 170            && b.k == ~ (CORE_ADDR) 0)
 171     return a;
 172
 173   /* We can 'and' a register with itself.  */
 174   else if (a.kind == pvk_register
 175            && b.kind == pvk_register
 176            && a.reg == b.reg
 177            && a.k == b.k)
 178     return a;
 179
 180   /* Otherwise, we don't know.  */
 181   else
 182     return pv_unknown ();
 183 }
 184
 185
 186 \f
 187 /* Examining prologue values.  */
 188
 189 int
 190 pv_is_identical (pv_t a, pv_t b)
 191 {
 192   if (a.kind != b.kind)
 193     return 0;
 194
 195   switch (a.kind)
 196     {
 197     case pvk_unknown:
 198       return 1;
 199     case pvk_constant:
 200       return (a.k == b.k);
 201     case pvk_register:
 202       return (a.reg == b.reg && a.k == b.k);
 203     default:
 204       gdb_assert_not_reached ("unexpected prologue value kind");
 205     }
 206 }
 207
 208
 209 int
 210 pv_is_constant (pv_t a)
 211 {
 212   return (a.kind == pvk_constant);
 213 }
 214
 215
 216 int
 217 pv_is_register (pv_t a, int r)
 218 {
 219   return (a.kind == pvk_register
 220           && a.reg == r);
 221 }
 222
 223
 224 int
 225 pv_is_register_k (pv_t a, int r, CORE_ADDR k)
 226 {
 227   return (a.kind == pvk_register
 228           && a.reg == r
 229           && a.k == k);
 230 }
 231
 232
 233 enum pv_boolean
 234 pv_is_array_ref (pv_t addr, CORE_ADDR size,
 235                  pv_t array_addr, CORE_ADDR array_len,
 236                  CORE_ADDR elt_size,
 237                  int *i)
 238 {
 239   /* Note that, since .k is a CORE_ADDR, and CORE_ADDR is unsigned, if
 240      addr is *before* the start of the array, then this isn't going to
 241      be negative...  */
 242   pv_t offset = pv_subtract (addr, array_addr);
 243
 244   if (offset.kind == pvk_constant)
 245     {
 246       /* This is a rather odd test.  We want to know if the SIZE bytes
 247          at ADDR don't overlap the array at all, so you'd expect it to
 248          be an || expression: "if we're completely before || we're
 249          completely after".  But with unsigned arithmetic, things are
 250          different: since it's a number circle, not a number line, the
 251          right values for offset.k are actually one contiguous range.  */
 252       if (offset.k <= -size
 253           && offset.k >= array_len * elt_size)
 254         return pv_definite_no;
 255       else if (offset.k % elt_size != 0
 256                || size != elt_size)
 257         return pv_maybe;
 258       else
 259         {
 260           *i = offset.k / elt_size;
 261           return pv_definite_yes;
 262         }
 263     }
 264   else
 265     return pv_maybe;
 266 }
 267
 268
 269 \f
 270 /* Areas.  */
 271
 272
 273 /* A particular value known to be stored in an area.
 274
 275    Entries form a ring, sorted by unsigned offset from the area's base
 276    register's value.  Since entries can straddle the wrap-around point,
 277    unsigned offsets form a circle, not a number line, so the list
 278    itself is structured the same way --- there is no inherent head.
 279    The entry with the lowest offset simply follows the entry with the
 280    highest offset.  Entries may abut, but never overlap.  The area's
 281    'entry' pointer points to an arbitrary node in the ring.  */
 282 struct area_entry
 283 {
 284   /* Links in the doubly-linked ring.  */
 285   struct area_entry *prev, *next;
 286
 287   /* Offset of this entry's address from the value of the base
 288      register.  */
 289   CORE_ADDR offset;
 290
 291   /* The size of this entry.  Note that an entry may wrap around from
 292      the end of the address space to the beginning.  */
 293   CORE_ADDR size;
 294
 295   /* The value stored here.  */
 296   pv_t value;
 297 };
 298
 299
 300 struct pv_area
 301 {
 302   /* This area's base register.  */
 303   int base_reg;
 304
 305   /* The mask to apply to addresses, to make the wrap-around happen at
 306      the right place.  */
 307   CORE_ADDR addr_mask;
 308
 309   /* An element of the doubly-linked ring of entries, or zero if we
 310      have none.  */
 311   struct area_entry *entry;
 312 };
 313
 314
 315 struct pv_area *
 316 make_pv_area (int base_reg, int addr_bit)
 317 {
 318   struct pv_area *a = (struct pv_area *) xmalloc (sizeof (*a));
 319
 320   memset (a, 0, sizeof (*a));
 321
 322   a->base_reg = base_reg;
 323   a->entry = 0;
 324
 325   /* Remember that shift amounts equal to the type's width are
 326      undefined.  */
 327   a->addr_mask = ((((CORE_ADDR) 1 << (addr_bit - 1)) - 1) << 1) | 1;
 328
 329   return a;
 330 }
 331
 332
 333 /* Delete all entries from AREA.  */
 334 static void
 335 clear_entries (struct pv_area *area)
 336 {
 337   struct area_entry *e = area->entry;
 338
 339   if (e)
 340     {
 341       /* This needs to be a do-while loop, in order to actually
 342          process the node being checked for in the terminating
 343          condition.  */
 344       do
 345         {
 346           struct area_entry *next = e->next;
 347
 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 precedes 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
 471           e->prev->next = e->next;
 472           e->next->prev = e->prev;
 473
 474           xfree (e);
 475           e = next;
 476         }
 477
 478       /* Move the area's pointer to the next remaining entry.  This
 479          will also zero the pointer if we've deleted all the entries.  */
 480       area->entry = e;
 481     }
 482
 483   /* Now, there are no entries overlapping us, and area->entry is
 484      either zero or pointing at the closest entry after us.  We can
 485      just insert ourselves before that.
 486
 487      But if we're storing an unknown value, don't bother --- that's
 488      the default.  */
 489   if (value.kind == pvk_unknown)
 490     return;
 491   else
 492     {
 493       CORE_ADDR offset = addr.k;
 494       struct area_entry *e = (struct area_entry *) xmalloc (sizeof (*e));
 495
 496       e->offset = offset;
 497       e->size = size;
 498       e->value = value;
 499
 500       if (area->entry)
 501         {
 502           e->prev = area->entry->prev;
 503           e->next = area->entry;
 504           e->prev->next = e->next->prev = e;
 505         }
 506       else
 507         {
 508           e->prev = e->next = e;
 509           area->entry = e;
 510         }
 511     }
 512 }
 513
 514
 515 pv_t
 516 pv_area_fetch (struct pv_area *area, pv_t addr, CORE_ADDR size)
 517 {
 518   /* If we have no entries, or we can't decide how ADDR relates to the
 519      entries we do have, then the value is unknown.  */
 520   if (! area->entry
 521       || pv_area_store_would_trash (area, addr))
 522     return pv_unknown ();
 523   else
 524     {
 525       CORE_ADDR offset = addr.k;
 526       struct area_entry *e = find_entry (area, offset);
 527
 528       /* If this entry exactly matches what we're looking for, then
 529          we're set.  Otherwise, say it's unknown.  */
 530       if (e->offset == offset && e->size == size)
 531         return e->value;
 532       else
 533         return pv_unknown ();
 534     }
 535 }
 536
 537
 538 int
 539 pv_area_find_reg (struct pv_area *area,
 540                   struct gdbarch *gdbarch,
 541                   int reg,
 542                   CORE_ADDR *offset_p)
 543 {
 544   struct area_entry *e = area->entry;
 545
 546   if (e)
 547     do
 548       {
 549         if (e->value.kind == pvk_register
 550             && e->value.reg == reg
 551             && e->value.k == 0
 552             && e->size == register_size (gdbarch, reg))
 553           {
 554             if (offset_p)
 555               *offset_p = e->offset;
 556             return 1;
 557           }
 558
 559         e = e->next;
 560       }
 561     while (e != area->entry);
 562
 563   return 0;
 564 }
 565
 566
 567 void
 568 pv_area_scan (struct pv_area *area,
 569               void (*func) (void *closure,
 570                             pv_t addr,
 571                             CORE_ADDR size,
 572                             pv_t value),
 573               void *closure)
 574 {
 575   struct area_entry *e = area->entry;
 576   pv_t addr;
 577
 578   addr.kind = pvk_register;
 579   addr.reg = area->base_reg;
 580
 581   if (e)
 582     do
 583       {
 584         addr.k = e->offset;
 585         func (closure, addr, e->size, e->value);
 586         e = e->next;
 587       }
 588     while (e != area->entry);
 589 }