revng-revng/lib/StackAnalysis/OVERVIEW.md

This document describes from an high level point of view the stack analysis and its components.

The StackAnalysis pass

The StackAnalysis pass is where everything begins. Its run method does the following:

• It keeps an instance of the Cache class, which holds the results of the analyses for each function analyzed so far. The Cache also identifies, for each function call, where the return address is stored (i.e., the link register or the top of the stack) and what's the most common place to store the return address (an information that will be employed for functions that have no direct calls).
• It identifies the function entry points. They are divided in two sets, one for the entry points that are highly likely to represent a function (in particular, those that are target of a direct call) and then the rest of possible candidates.
• It runs the analysis on the first set of functions.
• It runs the analysis on the functions of the second set whose entry basic block has not been identified as being part of a function of the first set.
• It collects the results of the analysis in ResultsPool.
• It produces the final version of the results contained in ResultsPool, obtaining a FunctionsSummary object.

The InterproceduralAnalysis

What we called the analysis is actually InterproceduralAnalysis. A run of the InterproceduralAnalysis analyzes a single function and collects the results of the analysis in a ResultsPool object. The ResultsPool contains intermediate information that will be then merged into the final object exposed by the analysis, i.e., FunctionsSummary. Note that the Cache is used exclusively for handling function calls during the intraprocedural analysis, it has nothing to do with the collection of the final results, which is handled by ResultsPool and FunctionsSummary.

To perform the analysis, InterproceduralAnalysis performs one or more Intraprocedural::Analysis, starting from the entry point, but, if necessary, analyzing all the functions in the call graph starting from the original entry point.

In practice, each time an Intraprocedural::Analysis meets a call site targeting a function not already analyzed (i.e., not present in Cache), the Intraprocedural::Analysis is suspended and the control is returned to the InterproceduralAnalysis that will start a new Intraprocedural::Analysis for the callee. The list of suspended Intraprocedural::Analysis is recorded on a stack, whose top element is the currently running analysis.

The InterproceduralAnalysis also handles recursion. In case the Intraprocedural::Analysis has been suspended due to a uncached function call, the interprocedural part will detect if the callee is a function already present in the stack of the currently in-progress analyses and, in such case, it will inject a temporary top entry in the cache. The intraprocedural analysis can now proceed with a safe (and pessimistic) assumption.

Once the analysis of the recursive function is terminated, as usual, it is recorded in the cache. If the result is different from the cached one, the analysis is restarted from scratch, but in this case the recursive call site will use the more accurate information provided by the last analysis. This process is repeated until a fixed point is reached, i.e., the result of the analysis matches the one already present in the cache.

The intraprocedural analysis (stack analysis)

The core goal of Intraprocedural::Analysis is to analyze how the registers are used in a function and the extension of the function itself.

In particular, the intraprocedural analysis can:

• detect if a register is a callee-saved register in a function;
• if an indirect jump is a return instruction;
• if a function misbehaves with the stack and should therefore be considered a "fake function", i.e., a function to inline in the callers;

The intraprocedural analysis (in the StackAnalysis::Intraprocedural namespace) is an instance of the MonotoneFramework class, and, as such, it has a couple of interesting parts: the lattice and the transfer function.

The intraprocedural analysis is a forward analysis.

The lattice

The lattice is defined by the Element class. The Element class is basically a container for a set of AddressSpace. An Element can have 0 or 3 address spaces.

The first AddressSpace (or "alias domain") represents the CPU state (CPU), the second the global variables and the heap (GLB), while the third is for the the stack frame of the current function (SP0).

An AddressSpace tracks its content in the form of "slots" (ASSlot), i.e., a pair of the identifier of an address space and an offset within it. For the CPU address space, the offset represent the index of the CSV.

The GLB address spaces is also used to track constants. This means that the constant 42 will be represented as an ASSlot relative to GLB with offset 42 (GLB+42).

Note that our analyses currently ignore overlapping slots. Note also that overlapping slots are not possible in the CPU address space (CSVs never alias).

An AddressSpace associates to each slot a Value. A Value is composed by two ASSlot fields: a "direct content", i.e., the content of the slot in a certain program point (according to our analysis) and a "tag". A tag represents the fact that we are not able to track the actual content of that slot statically, but we know that it contains the value that another slot contained at the entry of the function. The tag is useful to represent, e.g., the information that a certain stack slot (where the value of a callee-saved register is saved) contains the initial value of a register, or that an indirect jump is targeting a Value representing the initial value, e.g., of the link register. In the latter case, we basically proved that the indirect jump is actually a return instruction.

The intraprocedural analysis associates to each SSA value an element of the lattice. However, only the lattice element at the end of the basic block currently being processed is of our interest (so that it can be propagated to its successors).

The transfer function

The transfer function of the intraprocedural analysis handles mainly the following types of instructions:

• StoreInst: a store has an address and a value to store, they will be both associated to a Value. If the address Value has a direct content, the AddressSpace associated to the direct content ASSlot will be updated at the appropriate offset.

• LoadInst: if the Value associated to the pointer operand has a direct content, we will look up in the corresponding address space at the corresponding offset if have recorded a Value. If so, the result is that Value. Otherwise this means that we are not aware of any store instruction targeting that address, therefore, the resulting Value won't have a direct content but just a tag representing the loaded address.

• TerminatorInst: terminator instructions go through a classification depending on the context in which they are performed. For instance, an indirect jump might be detected as a return instruction if it's jumping to a Value tagged with the link register ASSlot and the stack is no higher than how it was at entry of the function.

  A TerminatorInst can also represent a function call, in such case, its callee (if not indirect) is looked up into the Cache, if it's available the result of its analysis replace the current state of the AddressSpaces, otherwise the intraprocedural analysis is suspended and the control is returned to the interprocedural part as described above.

Other basic instructions are handled in the straightforward way, e.g., addition.

The ABI analysis

As part of the finalization of the results of the intraprocedural analysis (Analysis::createSummary), the ABI analysis is performed. The goal of the ABI analysis is to detect arguments and return values of function and function calls.

The ABI IR

The ABI analysis is performed on a custom IR, the ABI IR, which is produced by the intraprocedural analysis during its execution. The main motivating reason for having this IR is to facilitate debugging and, most importantly, being able to perform backward analyses easily.

The ABI IR is quite simple: the ABIIRFunction is a container of ABIIRBasicBlocks which in turn are containers for ABIIRInstructions. Each basic block has links to its successors and predecessors.

An ABIIRInstruction can be of the following types:

• Load: a read from an ASSlot;
• Store: a write to an ASSlot (what is being written, is of no interest);
• DirectCall: a function call for which a result of a previously run ABI analysis is available.
• IndirectCall: a function call about which nothing is known.

The analyses

The FunctionABI class is responsible for performing all the analyses concerning the ABI. In particular, the analyze method performs two sets of analyses: the first set are forward, while the second one is backward.

Each set can be further divided into two groups: the analyses concerning the function itself and analyses concerning the function calls.

Each function-level analysis starts with a Default instance, then, each time a memory access to a certain CSV is met, the Default instance is cloned and associated to that CSV, whose analysis then proceeds independently.

The same holds for function call-level analyses, with the distinction that the same "lazy" instantiation of a set of analyses happens also each time a call site is met.

The set of function-level analyses contain all the function call-level analyses too so that their result can be used by the calling function performing function call-level analyses (as if they were inlined).

Each analysis is wrapped in an Inhibitor class, which, as the name suggests, is used to inhibit the wrapped analysis from applying the transfer function while walking the IR. Function-level analyses are never inhibited. Function call-level analyses, instead, start as inhibited and, once the corresponding function call is met, they are enabled. This helps us to simulate the beginning of the analysis in that point. The transfer function of a function call analysis reaching for the second time the function call is the unknown function call transfer function.

For the list of forward, backward, function and function call analyses, consult the source code and the .dot files used to generate them.

Merging the results

At the end of all of the analyses, the ResultsPool object will contain a summary of all the recovered information such as the basic block composing a function, the type of function, the status of each registers in terms of being an argument or a return value for each function and for each function call and so on.

These information, and, specifically the last two pieces of information, have to be merged together in order to produce more accurate information or identify contradictions. This step is performed in ResultsPool::finalize.

Basically the idea is that if for a certain register we have a Yes from a call site and a NoOrDead from the function itself, we will produce as a final information for the call site Dead. We will produce Dead for the function too only in case all of the call sites agree.

Ad-hoc handling of peculiar situations

For various reasons, in part concerning our code generation pipeline and in part due to certain practices in compiler backends, we have to handle certain situations in an ad-hoc way to avoid mistakes.

In the following we will discuss the situations we currently handle.

Fake functions

Consider the following example of ARM code:

_start:
    push {lr}
    bl prologue
    ldr r0, [r0]
    b epilogue

prologue:
    push {r0}
    push {r1}
    bx lr

epilogue:
    pop {r1}
    pop {r0}
    pop {lr}
    bx lr

The compiler (or the developer) decided to outline the function prologue and epilogue, likely for code size reduction reasons. In this situation we don't really want to consider prologue and epilogue as standalone functions, for two reasons: they manipulate the stack in weird ways and prevent us from identifying callee-saved registers.

The jump to the epilogue is not a problem since it will automatically considered part of each function jumping there. On the other hand, we need to make sure that we can correctly identify prologue as a fake function, and, therefore, inline it in the caller.

To do this, we can note that at the end of the "function" the stack is higher than it was at the beginning. No sane function call would allow this. Therefore, we mark prologue as a fake function.

Note, on the other hand, than having a stack lower than it was at the beginning is allowed, since certain caller conventions mandate to the callee the cleanup of stack arguments (e.g., the Windows PASCAL calling convention).

As a consequence, when we analyze a terminator during the intraprocedural analysis (handleTerminator method), when we meet an instruction that jumps to the initial content of the link register, we understand it's a return, but if we see that the stack is higher than it initially was, we mark the functions as fake and resume the analysis of the caller (if any), in which we will inline the function call.

Consider now the following a variation of the previous snippet:

_start:
    push {lr}
    add sp,sp,-8
    bl prologue
    ldr r0, [r0]
    b epilogue

prologue:
    str r1,[sp,0]
    str r0,[sp,4]
    bx lr

epilogue:
    pop {r1}
    pop {r0}
    pop {lr}
    bx lr

In this case, the stack pointer is not touched by the prologue function. Therefore, the previous criteria is not effective. In this case we observe another fact: the prologue function writes in SP0+0 and SP0+4, which seem to be stack argument. This is fine, however we keep track of this. The next thing we observe is that the same stack slots are read by the caller (in the epilogue basic block). Under our assumptions, this is not allowed, since no return value is passed (directly) on the stack and stack arguments are no longer valid after the function returns. Therefore, we mark the called function as fake.

This analysis is performed by the StackAnalysis::IncoherentCallsAnalysis analysis, which is performed on the ABI IR. The analysis is triggered by the findIncoherentFunctions function in the createSummary method of the intraprocedural analysis, after the ABI analysis has been run.

Forwarded arguments

Consider the following snippet of x86-64 assembly:

push_pop:
    push rax
    pop rdx
    ret

This code is sometimes emitted by the compiler with the only goal of growing and decreasing the stack height. The rax and rdx registers do not contain anything meaningful.

The problem with this snippet is that, according to our analyses, rax is an argument and rdx is a return value, while, obviously this is not the case.

To detect this situation, the IntraproceduralFunctionSummary, which holds the final result of the intraprocedural analysis of a functions, has a process method the pattern matches it: if a return value is tagged with the initial value of different register and that value is also stored in a stack slot, we mark it as a forwarded argument.

Statements about such registers in terms of being arguments/return values will be weakened.

Identity loads

Identity loads are a particular type of load instructions. Consider the following x86-64 pseudo code:

a = rax & 0xffff0000
b = 0xaaaa
rax = a | b

This snippet is the result of writing only the lowest 16 bits of rax (with 0xAAAA), however, from our point of view we have a read of rax before any write and would, therefore, consider it an argument. This load is an identity load, a load whose value will end up as is in itself.

Identity loads are ignored completely. They are not even part of the ABI IR.

The Cache is in charge to identify and keep track of identity loads (Cache::identifyIdentityLoads).