2 # Script that tries to find how much stack space each function in an
5 # Copyright (C) 2008 Kevin O'Connor <kevin@koconnor.net>
7 # This file may be distributed under the terms of the GNU GPLv3 license.
10 # objdump -m i386 -M i8086 -M suffix -d out/rom16.o | tools/checkstack.py
15 # Functions that change stacks
16 STACKHOP = ['__send_disk_op']
17 # List of functions we can assume are never called.
18 #IGNORE = ['panic', '__dprintf']
22 #funcname1[preamble_stack_usage,max_usage_with_callers]:
23 # insn_addr:called_function [usage_at_call_point+caller_preamble,total_usage]
25 #funcname2[p,m,max_usage_to_yield_point]:
26 # insn_addr:called_function [u+c,t,usage_to_yield_point]
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.
34 maxyieldusage = doesyield = 0
35 if info[3] is not None:
36 maxyieldusage = info[3]
42 for insnaddr, calladdr, usage in info[6]:
43 callinfo = funcs.get(calladdr)
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
56 if funcnameroot in STACKHOP:
59 if callinfo[4] is not None:
61 if usage > maxyieldusage:
64 totusage = usage + callinfo[2]
65 if totusage > maxusage:
67 if callinfo[4] is not None:
69 totyieldusage = usage + callinfo[4]
70 if totyieldusage > maxyieldusage:
71 maxyieldusage = totyieldusage
74 info[4] = maxyieldusage
77 # Try to arrange output so that functions that call each other are
79 def orderfuncs(funcaddrs, availfuncs):
80 l = [(availfuncs[funcaddr][5], availfuncs[funcaddr][0], funcaddr)
81 for funcaddr in funcaddrs if funcaddr in availfuncs]
86 count, name, funcaddr = l.pop(0)
87 if funcaddr not in availfuncs:
89 calladdrs = [calls[1] for calls in availfuncs[funcaddr][6]]
90 del availfuncs[funcaddr]
91 out = out + orderfuncs(calladdrs, availfuncs) + [funcaddr]
94 # Update function info with a found "yield" point.
95 def noteYield(info, stackusage):
97 if prevyield is None or prevyield < stackusage:
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.
105 info[6].append((insnaddr, calladdr, stackusage))
106 subfuncs[(calladdr, stackusage)] = 1
109 re_func = re.compile(r'^(?P<funcaddr>' + hex_s + r') <(?P<func>.*)>:$')
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)$')
118 # funcs[funcaddr] = [funcname, basicstackusage, maxstackusage
119 # , yieldusage, maxyieldusage, totalcalls
120 # , [(insnaddr, calladdr, stackusage), ...]]
121 funcs = {-1: ['<indirect>', 0, 0, None, None, 0, []]}
127 for line in sys.stdin.readlines():
128 m = re_func.match(line)
131 funcaddr = int(m.group('funcaddr'), 16)
132 funcs[funcaddr] = cur = [m.group('func'), 0, None, None, None, 0, []]
137 m = re_asm.match(line)
139 insn = m.group('insn')
141 im = re_usestack.match(insn)
143 if insn.startswith('pushl') or insn.startswith('pushfl'):
146 elif insn.startswith('pushw') or insn.startswith('pushfw'):
149 stackusage += int(im.group('num'), 16)
152 if insn == 'movl %esp,%ebp':
153 # Still part of initial header
158 insnaddr = m.group('insnaddr')
159 calladdr = m.group('calladdr')
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)
174 calladdr = int(calladdr, 16)
177 # Inter-function jump.
179 elif insn.startswith('j'):
181 noteCall(cur, subfuncs, insnaddr, calladdr, 0)
182 elif insn.startswith('calll'):
183 noteCall(cur, subfuncs, insnaddr, calladdr, stackusage + 4)
185 print "unknown call", ref
186 noteCall(cur, subfuncs, insnaddr, calladdr, stackusage)
187 # Reset stack usage to preamble usage
190 #print "other", repr(line)
192 # Calculate maxstackusage
193 for funcaddr, info in funcs.items():
194 if info[2] is not None:
196 calcmaxstack(funcs, funcaddr)
198 # Sort functions for output
199 funcaddrs = orderfuncs(funcs.keys(), funcs.copy())
203 for funcaddr in funcaddrs:
204 name, basicusage, maxusage, yieldusage, maxyieldusage, count, calls = \
206 if maxusage == 0 and maxyieldusage is None:
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))
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)
224 if __name__ == '__main__':