Re: RFA: general prologue analysis framework

[Eli Zaretskii <eliz@gnu.org>]

> From: Jim Blandy <jimb@redhat.com>
> Date: Thu, 06 Oct 2005 16:51:11 -0700
> 
> + /* When we analyze a prologue, we're really doing 'abstract
> +    interpretation' or 'pseudo-evaluation': running the function's code
> +    in simulation, but using conservative approximations of the values
> +    it would have when it actually runs.  For example, if our function
> +    starts with the instruction:
> + 
> +       addi r1, 42     # add 42 to r1
> + 
> +    we don't know exactly what value will be in r1 after executing this
> +    instruction, but we do know it'll be 42 greater than its original
> +    value.
> + 
> +    If we then see an instruction like:
> + 
> +       addi r1, 22     # add 22 to r1
> + 
> +    we still don't know what r1's value is, but again, we can say it is
> +    now 64 greater than its original value.
> + 
> +    If the next instruction were:
> + 
> +       mov r2, r1      # set r2 to r1's value
> + 
> +    then we can say that r2's value is now the original value of r1
> +    plus 64.
> + 
> +    It's common for prologues to save registers on the stack, so we'll
> +    need to track the values of stack frame slots, as well as the
> +    registers.  So after an instruction like this:
> + 
> +       mov (fp+4), r2
> + 
> +    Then we'd know that the stack slot four bytes above the frame
> +    pointer holds the original value of r1 plus 64.
> + 
> +    And so on.
> + 
> +    Of course, this can only go so far before it gets unreasonable.  If
> +    we wanted to be able to say anything about the value of r1 after
> +    the instruction:
> + 
> +       xor r1, r3      # exclusive-or r1 and r3, place result in r1
> + 
> +    then things would get pretty complex.  But remember, we're just
> +    doing a conservative approximation; if exclusive-or instructions
> +    aren't relevant to prologues, we can just say r1's value is now
> +    'unknown'.  We can ignore things that are too complex, if that loss
> +    of information is acceptable for our application.
> + 
> +    So when I say "conservative approximation" here, what I mean is an
> +    approximation that is either accurate, or marked "unknown", but
> +    never inaccurate.
> +    
> +    Once you've reached the current PC, or an instruction that you
> +    don't know how to simulate, you stop.  Now you can examine the
> +    state of the registers and stack slots you've kept track of.
> + 
> +    - To see how large your stack frame is, just check the value of the
> +      stack pointer register; if it's the original value of the SP
> +      minus a constant, then that constant is the stack frame's size.
> +      If the SP's value has been marked as 'unknown', then that means
> +      the prologue has done something too complex for us to track, and
> +      we don't know the frame size.
> + 
> +    - To see where we've saved the previous frame's registers, we just
> +      search the values we've tracked --- stack slots, usually, but
> +      registers, too, if you want --- for something equal to the
> +      register's original value.  If the ABI suggests a standard place
> +      to save a given register, then we can check there first, but
> +      really, anything that will get us back the original value will
> +      probably work.
> + 
> +    Sure, this takes some work.  But prologue analyzers aren't
> +    quick-and-simple pattern patching to recognize a few fixed prologue
> +    forms any more; they're big, hairy functions.  Along with inferior
> +    function calls, prologue analysis accounts for a substantial
> +    portion of the time needed to stabilize a GDB port.  So I think
> +    it's worthwhile to look for an approach that will be easier to
> +    understand and maintain.  In the approach used here:
> + 
> +    - It's easier to see that the analyzer is correct: you just see
> +      whether the analyzer properly (albiet conservatively) simulates
> +      the effect of each instruction.
> + 
> +    - It's easier to extend the analyzer: you can add support for new
> +      instructions, and know that you haven't broken anything that
> +      wasn't already broken before.
> + 
> +    - It's orthogonal: to gather new information, you don't need to
> +      complicate the code for each instruction.  As long as your domain
> +      of conservative values is already detailed enough to tell you
> +      what you need, then all the existing instruction simulations are
> +      already gathering the right data for you.
> + 
> +    A 'struct prologue_value' is a conservative approximation of the
> +    real value the register or stack slot will have.  */

Jim, I'd be thrilled to see this text in gdbint.texinfo (if and when
the patch is committed), perhaps with a few more general words about
prologue analysis, which is currently completely undocumented.