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 "prologue-value.h"
  21 #include "regcache.h"
  22
  23 \f
  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 \f
  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 \f
 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 \f
 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 = (struct pv_area *) xmalloc (sizeof (*a));
 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 = (struct area_entry *) xmalloc (sizeof (*e));
 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 }