gdb/prologue-value.c

   1 /* Prologue value handling for GDB.
   2    Copyright (C) 2003-2018 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 pv_area::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 /* See prologue-value.h.  */
 300
 301 pv_area::pv_area (int base_reg, int addr_bit)
 302   : m_base_reg (base_reg),
 303     /* Remember that shift amounts equal to the type's width are
 304        undefined.  */
 305     m_addr_mask (((((CORE_ADDR) 1 << (addr_bit - 1)) - 1) << 1) | 1),
 306     m_entry (nullptr)
 307 {
 308 }
 309
 310 /* See prologue-value.h.  */
 311
 312 void
 313 pv_area::clear_entries ()
 314 {
 315   struct area_entry *e = m_entry;
 316
 317   if (e)
 318     {
 319       /* This needs to be a do-while loop, in order to actually
 320          process the node being checked for in the terminating
 321          condition.  */
 322       do
 323         {
 324           struct area_entry *next = e->next;
 325
 326           xfree (e);
 327           e = next;
 328         }
 329       while (e != m_entry);
 330
 331       m_entry = 0;
 332     }
 333 }
 334
 335
 336 pv_area::~pv_area ()
 337 {
 338   clear_entries ();
 339 }
 340
 341
 342 /* See prologue-value.h.  */
 343
 344 bool
 345 pv_area::store_would_trash (pv_t addr)
 346 {
 347   /* It may seem odd that pvk_constant appears here --- after all,
 348      that's the case where we know the most about the address!  But
 349      pv_areas are always relative to a register, and we don't know the
 350      value of the register, so we can't compare entry addresses to
 351      constants.  */
 352   return (addr.kind == pvk_unknown
 353           || addr.kind == pvk_constant
 354           || (addr.kind == pvk_register && addr.reg != m_base_reg));
 355 }
 356
 357
 358 /* See prologue-value.h.  */
 359
 360 struct pv_area::area_entry *
 361 pv_area::find_entry (CORE_ADDR offset)
 362 {
 363   struct area_entry *e = m_entry;
 364
 365   if (! e)
 366     return 0;
 367
 368   /* If the next entry would be better than the current one, then scan
 369      forward.  Since we use '<' in this loop, it always terminates.
 370
 371      Note that, even setting aside the addr_mask stuff, we must not
 372      simplify this, in high school algebra fashion, to
 373      (e->next->offset < e->offset), because of the way < interacts
 374      with wrap-around.  We have to subtract offset from both sides to
 375      make sure both things we're comparing are on the same side of the
 376      discontinuity.  */
 377   while (((e->next->offset - offset) & m_addr_mask)
 378          < ((e->offset - offset) & m_addr_mask))
 379     e = e->next;
 380
 381   /* If the previous entry would be better than the current one, then
 382      scan backwards.  */
 383   while (((e->prev->offset - offset) & m_addr_mask)
 384          < ((e->offset - offset) & m_addr_mask))
 385     e = e->prev;
 386
 387   /* In case there's some locality to the searches, set the area's
 388      pointer to the entry we've found.  */
 389   m_entry = e;
 390
 391   return e;
 392 }
 393
 394
 395 /* See prologue-value.h.  */
 396
 397 int
 398 pv_area::overlaps (struct area_entry *entry, CORE_ADDR offset, CORE_ADDR size)
 399 {
 400   /* Think carefully about wrap-around before simplifying this.  */
 401   return (((entry->offset - offset) & m_addr_mask) < size
 402           || ((offset - entry->offset) & m_addr_mask) < entry->size);
 403 }
 404
 405
 406 /* See prologue-value.h.  */
 407
 408 void
 409 pv_area::store (pv_t addr, CORE_ADDR size, pv_t value)
 410 {
 411   /* Remove any (potentially) overlapping entries.  */
 412   if (store_would_trash (addr))
 413     clear_entries ();
 414   else
 415     {
 416       CORE_ADDR offset = addr.k;
 417       struct area_entry *e = find_entry (offset);
 418
 419       /* Delete all entries that we would overlap.  */
 420       while (e && overlaps (e, offset, size))
 421         {
 422           struct area_entry *next = (e->next == e) ? 0 : e->next;
 423
 424           e->prev->next = e->next;
 425           e->next->prev = e->prev;
 426
 427           xfree (e);
 428           e = next;
 429         }
 430
 431       /* Move the area's pointer to the next remaining entry.  This
 432          will also zero the pointer if we've deleted all the entries.  */
 433       m_entry = e;
 434     }
 435
 436   /* Now, there are no entries overlapping us, and m_entry is
 437      either zero or pointing at the closest entry after us.  We can
 438      just insert ourselves before that.
 439
 440      But if we're storing an unknown value, don't bother --- that's
 441      the default.  */
 442   if (value.kind == pvk_unknown)
 443     return;
 444   else
 445     {
 446       CORE_ADDR offset = addr.k;
 447       struct area_entry *e = XNEW (struct area_entry);
 448
 449       e->offset = offset;
 450       e->size = size;
 451       e->value = value;
 452
 453       if (m_entry)
 454         {
 455           e->prev = m_entry->prev;
 456           e->next = m_entry;
 457           e->prev->next = e->next->prev = e;
 458         }
 459       else
 460         {
 461           e->prev = e->next = e;
 462           m_entry = e;
 463         }
 464     }
 465 }
 466
 467
 468 /* See prologue-value.h.  */
 469
 470 pv_t
 471 pv_area::fetch (pv_t addr, CORE_ADDR size)
 472 {
 473   /* If we have no entries, or we can't decide how ADDR relates to the
 474      entries we do have, then the value is unknown.  */
 475   if (! m_entry
 476       || store_would_trash (addr))
 477     return pv_unknown ();
 478   else
 479     {
 480       CORE_ADDR offset = addr.k;
 481       struct area_entry *e = find_entry (offset);
 482
 483       /* If this entry exactly matches what we're looking for, then
 484          we're set.  Otherwise, say it's unknown.  */
 485       if (e->offset == offset && e->size == size)
 486         return e->value;
 487       else
 488         return pv_unknown ();
 489     }
 490 }
 491
 492
 493 /* See prologue-value.h.  */
 494
 495 bool
 496 pv_area::find_reg (struct gdbarch *gdbarch, int reg, CORE_ADDR *offset_p)
 497 {
 498   struct area_entry *e = m_entry;
 499
 500   if (e)
 501     do
 502       {
 503         if (e->value.kind == pvk_register
 504             && e->value.reg == reg
 505             && e->value.k == 0
 506             && e->size == register_size (gdbarch, reg))
 507           {
 508             if (offset_p)
 509               *offset_p = e->offset;
 510             return true;
 511           }
 512
 513         e = e->next;
 514       }
 515     while (e != m_entry);
 516
 517   return false;
 518 }
 519
 520
 521 /* See prologue-value.h.  */
 522
 523 void
 524 pv_area::scan (void (*func) (void *closure,
 525                              pv_t addr,
 526                              CORE_ADDR size,
 527                              pv_t value),
 528                void *closure)
 529 {
 530   struct area_entry *e = m_entry;
 531   pv_t addr;
 532
 533   addr.kind = pvk_register;
 534   addr.reg = m_base_reg;
 535
 536   if (e)
 537     do
 538       {
 539         addr.k = e->offset;
 540         func (closure, addr, e->size, e->value);
 541         e = e->next;
 542       }
 543     while (e != m_entry);
 544 }