docs/func-params-returns.md

   1 Notes on complexities of function parameters/returns recovery
   2 =============================================================
   3
   4 1. A live-in set on function entry includes both parameters and
   5 preserved locations. To find out real parameters, liveness analysis
   6 should be performed after the dead code elimination of preservation
   7 instructions, which requires propagation and stack variable rewriting
   8 passes. The propagation in turn requires first-stage liveness (and
   9 reaching definitions) analysis.
  10
  11 2. Any value computed by a function may be its potential return.
  12 Unless we found *all* callers of a function, we can't write off
  13 some potential return. And any new discovered caller may extend
  14 set of returns. If a caller is not known, we should conservatively
  15 assume an initial proposition that any value which reaches exit
  16 may be live and used by a caller. That's why for such, caller-less
  17 functions, we initialize its live-out set to the set of registers
  18 which reach exit (as computed by reaching definitions, or, as a
  19 simplification, a union of all function defineds).
  20
  21 3. A particular issue with registers defined only along some paths
  22 of execution. Per p.2, such register is a potential return of the
  23 function. But as it's only defined on some paths, the only way to
  24 implement proper semantics for this case (that's, set the register
  25 to a particular value sometimes, and not change it other times) is
  26 to accept it as argument. Note that this happens completely
  27 automatically, the dataflow analysis is "smart" to "know" that this
  28 is needed. However, in each particular case, this fact may be not
  29 immediately obvious to a human. TODO: implement an annotation
  30 algorithm describing why this or that register got into a parameter
  31 set of a function. The summary or of this paragraph can be described
  32 as follows: superfluous returns lead to superfluous parameters.
  33
  34 4. All the above is especially aggravated for RISC architectures
  35 with large register sets. For example, a low-level assembly-coded
  36 routine written by a human may modify a number of registers (in
  37 preference of saving/restoring or using stack variables), while C
  38 routines calling them may be more reserved in register usage. This
  39 will cause original modifieds of assembly routine to leak into a
  40 caller, not being killed there, and leak into another caller,
  41 leading to long chains of functions with unrealistic returns (and
  42 parameters, as described in 3). Thus, it should be expected that
  43 in many realistic cases pure dataflow analysis won't be enough -
  44 it requires many diverse callers for each function, and only
  45 small subset of functions in a real program usually have this
  46 property. Instead, heuristics should be expected to be employed.
  47 This includes parameter and return filters based on ABI conventions,
  48 register order restrictions (registers are usually allocated to
  49 params/returns from an ordered sequence, so if some register is
  50 not in a params/returns set, any registers after it are unlikely
  51 candidates for real params/returns, etc. A useful heuristic also
  52 comes from p.3 - if some register is not defined along all execution
  53 paths, it's not a good candidate for returns, and thus params too. All
  54 these criteria are indeed heuristic - there can be some functions
  55 for which they are not true. Thus, a human should be able to select
  56 which heuristics to use, easily oversee results achieved, and be
  57 able to override them on a case by case basis.
  58
  59 5. Preserveds set is calculated in regards to function parameters.
  60 It may seem strange that a register which isn't defined locally
  61 (i.e. never explicitly saved/restored) is in preserveds set, but
  62 that means that it's a parameter, which serves as an arguments to
  63 another function, and that another function doesn't modify it, so
  64 it's really preserved for the current function. A more involved
  65 example is that some function has 2 paths: one modifying the
  66 parameter register, but ending with an infinite loop, while another
  67 path truly preserves that register, so overall semantics is
  68 preserving the register in the normal program flow, and this is
  69 signified in the preserveds.
  70
  71 6. Assuming RISC-style register calling convention, $sp being in
  72 function parameters after dataflow analysis may mean the function
  73 takes addresses of the objects on the stack. Otherwise, if they
  74 were just derefences of stack pointer, they would have been
  75 rewritten as stack variables. Note that referencing objects via
  76 stack pointer may create aliasing problems for rewritten stack
  77 vars.
  78
  79 Van Emmerik "3.4.5 Stack Pointer as Parameter" p.86/146 talks
  80 about the fact that with stack calling convention, stack pointer
  81 would appear to be a parameter of any function, and thus needs
  82 to be explicitly filtered out for final decompilation results.
  83 This is definitely true, but the previous paragraph talks about
  84 what it means that $sp is deemed as a parameter by the dataflow
  85 analysis even after stack variable rewriting pass (which should
  86 eliminate explicit $sp references).