tools/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  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 | tools/checkstack.py
  11
  12 import sys
  13 import re
  14
  15 # Functions that change stacks
  16 STACKHOP = ['__send_disk_op']
  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 # Find out maximum stack usage for a function
  30 def calcmaxstack(funcs, funcaddr):
  31     info = funcs[funcaddr]
  32     # Find max of all nested calls.
  33     maxusage = info[1]
  34     maxyieldusage = doesyield = 0
  35     if info[3] is not None:
  36         maxyieldusage = info[3]
  37         doesyield = 1
  38     info[2] = maxusage
  39     info[4] = info[3]
  40     seenbefore = {}
  41     totcalls = 0
  42     for insnaddr, calladdr, usage in info[6]:
  43         callinfo = funcs.get(calladdr)
  44         if callinfo is None:
  45             continue
  46         if callinfo[2] is None:
  47             calcmaxstack(funcs, calladdr)
  48         if callinfo[0] not in seenbefore:
  49             seenbefore[callinfo[0]] = 1
  50             totcalls += 1 + callinfo[5]
  51         funcnameroot = callinfo[0].split('.')[0]
  52         if funcnameroot in IGNORE:
  53             # This called function is ignored - don't contribute it to
  54             # the max stack.
  55             continue
  56         if funcnameroot in STACKHOP:
  57             if usage > maxusage:
  58                 maxusage = usage
  59             if callinfo[4] is not None:
  60                 doesyield = 1
  61                 if usage > maxyieldusage:
  62                     maxyieldusage = usage
  63             continue
  64         totusage = usage + callinfo[2]
  65         if totusage > maxusage:
  66             maxusage = totusage
  67         if callinfo[4] is not None:
  68             doesyield = 1
  69             totyieldusage = usage + callinfo[4]
  70             if totyieldusage > maxyieldusage:
  71                 maxyieldusage = totyieldusage
  72     info[2] = maxusage
  73     if doesyield:
  74         info[4] = maxyieldusage
  75     info[5] = totcalls
  76
  77 # Try to arrange output so that functions that call each other are
  78 # near each other.
  79 def orderfuncs(funcaddrs, availfuncs):
  80     l = [(availfuncs[funcaddr][5], availfuncs[funcaddr][0], funcaddr)
  81          for funcaddr in funcaddrs if funcaddr in availfuncs]
  82     l.sort()
  83     l.reverse()
  84     out = []
  85     while l:
  86         count, name, funcaddr = l.pop(0)
  87         if funcaddr not in availfuncs:
  88             continue
  89         calladdrs = [calls[1] for calls in availfuncs[funcaddr][6]]
  90         del availfuncs[funcaddr]
  91         out = out + orderfuncs(calladdrs, availfuncs) + [funcaddr]
  92     return out
  93
  94 # Update function info with a found "yield" point.
  95 def noteYield(info, stackusage):
  96     prevyield = info[3]
  97     if prevyield is None or prevyield < stackusage:
  98         info[3] = stackusage
  99
 100 # Update function info with a found "call" point.
 101 def noteCall(info, subfuncs, insnaddr, calladdr, stackusage):
 102     if (calladdr, stackusage) in subfuncs:
 103         # Already noted a nearly identical call - ignore this one.
 104         return
 105     info[6].append((insnaddr, calladdr, stackusage))
 106     subfuncs[(calladdr, stackusage)] = 1
 107
 108 hex_s = r'[0-9a-f]+'
 109 re_func = re.compile(r'^(?P<funcaddr>' + hex_s + r') <(?P<func>.*)>:$')
 110 re_asm = re.compile(
 111     r'^[ ]*(?P<insnaddr>' + hex_s
 112     + r'):\t.*\t(addr32 )?(?P<insn>.+?)[ ]*((?P<calladdr>' + hex_s
 113     + r') <(?P<ref>.*)>)?$')
 114 re_usestack = re.compile(
 115     r'^(push[f]?[lw])|(sub.* [$](?P<num>0x' + hex_s + r'),%esp)$')
 116
 117 def calc():
 118     # funcs[funcaddr] = [funcname, basicstackusage, maxstackusage
 119     #                    , yieldusage, maxyieldusage, totalcalls
 120     #                    , [(insnaddr, calladdr, stackusage), ...]]
 121     funcs = {-1: ['<indirect>', 0, 0, None, None, 0, []]}
 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 = [m.group('func'), 0, None, None, None, 0, []]
 133             stackusage = 0
 134             atstart = 1
 135             subfuncs = {}
 136             continue
 137         m = re_asm.match(line)
 138         if m is not None:
 139             insn = m.group('insn')
 140
 141             im = re_usestack.match(insn)
 142             if im is not None:
 143                 if insn.startswith('pushl') or insn.startswith('pushfl'):
 144                     stackusage += 4
 145                     continue
 146                 elif insn.startswith('pushw') or insn.startswith('pushfw'):
 147                     stackusage += 2
 148                     continue
 149                 stackusage += int(im.group('num'), 16)
 150
 151             if atstart:
 152                 if insn == 'movl   %esp,%ebp':
 153                     # Still part of initial header
 154                     continue
 155                 cur[1] = stackusage
 156                 atstart = 0
 157
 158             insnaddr = m.group('insnaddr')
 159             calladdr = m.group('calladdr')
 160             if calladdr is None:
 161                 if insn.startswith('lcallw'):
 162                     noteCall(cur, subfuncs, insnaddr, -1, stackusage + 4)
 163                     noteYield(cur, stackusage + 4)
 164                 elif insn.startswith('int'):
 165                     noteCall(cur, subfuncs, insnaddr, -1, stackusage + 6)
 166                     noteYield(cur, stackusage + 6)
 167                 elif insn.startswith('sti'):
 168                     noteYield(cur, stackusage)
 169                 else:
 170                     # misc instruction
 171                     continue
 172             else:
 173                 # Jump or call insn
 174                 calladdr = int(calladdr, 16)
 175                 ref = m.group('ref')
 176                 if '+' in ref:
 177                     # Inter-function jump.
 178                     pass
 179                 elif insn.startswith('j'):
 180                     # Tail call
 181                     noteCall(cur, subfuncs, insnaddr, calladdr, 0)
 182                 elif insn.startswith('calll'):
 183                     noteCall(cur, subfuncs, insnaddr, calladdr, stackusage + 4)
 184                 else:
 185                     print "unknown call", ref
 186                     noteCall(cur, subfuncs, insnaddr, calladdr, stackusage)
 187             # Reset stack usage to preamble usage
 188             stackusage = cur[1]
 189
 190         #print "other", repr(line)
 191
 192     # Calculate maxstackusage
 193     for funcaddr, info in funcs.items():
 194         if info[2] is not None:
 195             continue
 196         calcmaxstack(funcs, funcaddr)
 197
 198     # Sort functions for output
 199     funcaddrs = orderfuncs(funcs.keys(), funcs.copy())
 200
 201     # Show all functions
 202     print OUTPUTDESC
 203     for funcaddr in funcaddrs:
 204         name, basicusage, maxusage, yieldusage, maxyieldusage, count, calls = \
 205             funcs[funcaddr]
 206         if maxusage == 0 and maxyieldusage is None:
 207             continue
 208         yieldstr = ""
 209         if maxyieldusage is not None:
 210             yieldstr = ",%d" % maxyieldusage
 211         print "\n%s[%d,%d%s]:" % (name, basicusage, maxusage, yieldstr)
 212         for insnaddr, calladdr, stackusage in calls:
 213             callinfo = funcs.get(calladdr, ("<unknown>", 0, 0, 0, None))
 214             yieldstr = ""
 215             if callinfo[4] is not None:
 216                 yieldstr = ",%d" % (stackusage + callinfo[4])
 217             print "    %04s:%-40s [%d+%d,%d%s]" % (
 218                 insnaddr, callinfo[0], stackusage, callinfo[1]
 219                 , stackusage+callinfo[2], yieldstr)
 220
 221 def main():
 222     calc()
 223
 224 if __name__ == '__main__':
 225     main()