qemu/roms/seabios/scripts/checkstack.py

   1 #!/usr/bin/env python
   2 # Script that tries to find how much stack space each function in an
   3 # object is using.
   4 #
   5 # Copyright (C) 2008-2015  Kevin O'Connor <kevin@koconnor.net>
   6 #
   7 # This file may be distributed under the terms of the GNU GPLv3 license.
   8
   9 # Usage:
  10 #   objdump -m i386 -M i8086 -M suffix -d out/rom16.o | scripts/checkstack.py
  11
  12 import sys
  13 import re
  14
  15 # Functions that change stacks
  16 STACKHOP = ['stack_hop', 'stack_hop_back']
  17 # List of functions we can assume are never called.
  18 #IGNORE = ['panic', '__dprintf']
  19 IGNORE = ['panic']
  20
  21 OUTPUTDESC = """
  22 #funcname1[preamble_stack_usage,max_usage_with_callers]:
  23 #    insn_addr:called_function [usage_at_call_point+caller_preamble,total_usage]
  24 #
  25 #funcname2[p,m,max_usage_to_yield_point]:
  26 #    insn_addr:called_function [u+c,t,usage_to_yield_point]
  27 """
  28
  29 class function:
  30     def __init__(self, funcaddr, funcname):
  31         self.funcaddr = funcaddr
  32         self.funcname = funcname
  33         self.basic_stack_usage = 0
  34         self.max_stack_usage = None
  35         self.yield_usage = -1
  36         self.max_yield_usage = None
  37         self.total_calls = 0
  38         # called_funcs = [(insnaddr, calladdr, stackusage), ...]
  39         self.called_funcs = []
  40         self.subfuncs = {}
  41     # Update function info with a found "yield" point.
  42     def noteYield(self, stackusage):
  43         if self.yield_usage < stackusage:
  44             self.yield_usage = stackusage
  45     # Update function info with a found "call" point.
  46     def noteCall(self, insnaddr, calladdr, stackusage):
  47         if (calladdr, stackusage) in self.subfuncs:
  48             # Already noted a nearly identical call - ignore this one.
  49             return
  50         self.called_funcs.append((insnaddr, calladdr, stackusage))
  51         self.subfuncs[(calladdr, stackusage)] = 1
  52
  53 # Find out maximum stack usage for a function
  54 def calcmaxstack(info, funcs):
  55     if info.max_stack_usage is not None:
  56         return
  57     info.max_stack_usage = max_stack_usage = info.basic_stack_usage
  58     info.max_yield_usage = max_yield_usage = info.yield_usage
  59     total_calls = 0
  60     seenbefore = {}
  61     # Find max of all nested calls.
  62     for insnaddr, calladdr, usage in info.called_funcs:
  63         callinfo = funcs.get(calladdr)
  64         if callinfo is None:
  65             continue
  66         calcmaxstack(callinfo, funcs)
  67         if callinfo.funcname not in seenbefore:
  68             seenbefore[callinfo.funcname] = 1
  69             total_calls += callinfo.total_calls + 1
  70         funcnameroot = callinfo.funcname.split('.')[0]
  71         if funcnameroot in IGNORE:
  72             # This called function is ignored - don't contribute it to
  73             # the max stack.
  74             continue
  75         totusage = usage + callinfo.max_stack_usage
  76         totyieldusage = usage + callinfo.max_yield_usage
  77         if funcnameroot in STACKHOP:
  78             # Don't count children of this function
  79             totusage = totyieldusage = usage
  80         if totusage > max_stack_usage:
  81             max_stack_usage = totusage
  82         if callinfo.max_yield_usage >= 0 and totyieldusage > max_yield_usage:
  83             max_yield_usage = totyieldusage
  84     info.max_stack_usage = max_stack_usage
  85     info.max_yield_usage = max_yield_usage
  86     info.total_calls = total_calls
  87
  88 # Try to arrange output so that functions that call each other are
  89 # near each other.
  90 def orderfuncs(funcaddrs, availfuncs):
  91     l = [(availfuncs[funcaddr].total_calls
  92           , availfuncs[funcaddr].funcname, funcaddr)
  93          for funcaddr in funcaddrs if funcaddr in availfuncs]
  94     l.sort()
  95     l.reverse()
  96     out = []
  97     while l:
  98         count, name, funcaddr = l.pop(0)
  99         info = availfuncs.get(funcaddr)
 100         if info is None:
 101             continue
 102         calladdrs = [calls[1] for calls in info.called_funcs]
 103         del availfuncs[funcaddr]
 104         out = out + orderfuncs(calladdrs, availfuncs) + [info]
 105     return out
 106
 107 hex_s = r'[0-9a-f]+'
 108 re_func = re.compile(r'^(?P<funcaddr>' + hex_s + r') <(?P<func>.*)>:$')
 109 re_asm = re.compile(
 110     r'^[ ]*(?P<insnaddr>' + hex_s
 111     + r'):\t.*\t(addr32 )?(?P<insn>.+?)[ ]*((?P<calladdr>' + hex_s
 112     + r') <(?P<ref>.*)>)?$')
 113 re_usestack = re.compile(
 114     r'^(push[f]?[lw])|(sub.* [$](?P<num>0x' + hex_s + r'),%esp)$')
 115
 116 def main():
 117     unknownfunc = function(None, "<unknown>")
 118     indirectfunc = function(-1, '<indirect>')
 119     unknownfunc.max_stack_usage = indirectfunc.max_stack_usage = 0
 120     unknownfunc.max_yield_usage = indirectfunc.max_yield_usage = -1
 121     funcs = {-1: indirectfunc}
 122     cur = None
 123     atstart = 0
 124     stackusage = 0
 125
 126     # Parse input lines
 127     for line in sys.stdin.readlines():
 128         m = re_func.match(line)
 129         if m is not None:
 130             # Found function
 131             funcaddr = int(m.group('funcaddr'), 16)
 132             funcs[funcaddr] = cur = function(funcaddr, m.group('func'))
 133             stackusage = 0
 134             atstart = 1
 135             continue
 136         m = re_asm.match(line)
 137         if m is None:
 138             #print("other", repr(line))
 139             continue
 140         insn = m.group('insn')
 141
 142         im = re_usestack.match(insn)
 143         if im is not None:
 144             if insn.startswith('pushl') or insn.startswith('pushfl'):
 145                 stackusage += 4
 146                 continue
 147             elif insn.startswith('pushw') or insn.startswith('pushfw'):
 148                 stackusage += 2
 149                 continue
 150             stackusage += int(im.group('num'), 16)
 151
 152         if atstart:
 153             if '%esp' in insn or insn.startswith('leal'):
 154                 # Still part of initial header
 155                 continue
 156             cur.basic_stack_usage = stackusage
 157             atstart = 0
 158
 159         insnaddr = m.group('insnaddr')
 160         calladdr = m.group('calladdr')
 161         if calladdr is None:
 162             if insn.startswith('lcallw'):
 163                 cur.noteCall(insnaddr, -1, stackusage + 4)
 164                 cur.noteYield(stackusage + 4)
 165             elif insn.startswith('int'):
 166                 cur.noteCall(insnaddr, -1, stackusage + 6)
 167                 cur.noteYield(stackusage + 6)
 168             elif insn.startswith('sti'):
 169                 cur.noteYield(stackusage)
 170             else:
 171                 # misc instruction
 172                 continue
 173         else:
 174             # Jump or call insn
 175             calladdr = int(calladdr, 16)
 176             ref = m.group('ref')
 177             if '+' in ref:
 178                 # Inter-function jump.
 179                 pass
 180             elif insn.startswith('j'):
 181                 # Tail call
 182                 cur.noteCall(insnaddr, calladdr, 0)
 183             elif insn.startswith('calll'):
 184                 cur.noteCall(insnaddr, calladdr, stackusage + 4)
 185             elif insn.startswith('callw'):
 186                 cur.noteCall(insnaddr, calladdr, stackusage + 2)
 187             else:
 188                 print("unknown call", ref)
 189                 cur.noteCall(insnaddr, calladdr, stackusage)
 190         # Reset stack usage to preamble usage
 191         stackusage = cur.basic_stack_usage
 192
 193     # Calculate maxstackusage
 194     for info in funcs.values():
 195         calcmaxstack(info, funcs)
 196
 197     # Sort functions for output
 198     funcinfos = orderfuncs(funcs.keys(), funcs.copy())
 199
 200     # Show all functions
 201     print(OUTPUTDESC)
 202     for info in funcinfos:
 203         if info.max_stack_usage == 0 and info.max_yield_usage < 0:
 204             continue
 205         yieldstr = ""
 206         if info.max_yield_usage >= 0:
 207             yieldstr = ",%d" % info.max_yield_usage
 208         print("\n%s[%d,%d%s]:" % (info.funcname, info.basic_stack_usage
 209                                   , info.max_stack_usage, yieldstr))
 210         for insnaddr, calladdr, stackusage in info.called_funcs:
 211             callinfo = funcs.get(calladdr, unknownfunc)
 212             yieldstr = ""
 213             if callinfo.max_yield_usage >= 0:
 214                 yieldstr = ",%d" % (stackusage + callinfo.max_yield_usage)
 215             print("    %04s:%-40s [%d+%d,%d%s]" % (
 216                 insnaddr, callinfo.funcname, stackusage
 217                 , callinfo.basic_stack_usage
 218                 , stackusage+callinfo.max_stack_usage, yieldstr))
 219
 220 if __name__ == '__main__':
 221     main()