blob: 84bd778d4cdba9f7f0532021f14ba66fb8c0ff5c [file] [log] [blame]
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -04001#!/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:
Kevin O'Connor7173f6f2009-05-27 22:23:33 -040010# objdump -m i386 -M i8086 -M suffix -d out/rom16.reloc.o | tools/checkstack.py
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -040011
12import sys
13import re
14
Kevin O'Connora979c1c2010-03-09 20:01:35 -050015# Functions that change stacks
16STACKHOP = ['__send_disk_op']
Kevin O'Connorf5cb0792008-06-07 10:11:36 -040017# List of functions we can assume are never called.
Kevin O'Connora979c1c2010-03-09 20:01:35 -050018#IGNORE = ['panic', '__dprintf']
19IGNORE = ['panic']
20
21OUTPUTDESC = """
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"""
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -040028
29# Find out maximum stack usage for a function
Kevin O'Connor95cde272008-07-13 10:59:11 -040030def calcmaxstack(funcs, funcaddr):
31 info = funcs[funcaddr]
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -040032 # Find max of all nested calls.
Kevin O'Connora979c1c2010-03-09 20:01:35 -050033 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]:
Kevin O'Connor95cde272008-07-13 10:59:11 -040043 callinfo = funcs[calladdr]
44 if callinfo[2] is None:
45 calcmaxstack(funcs, calladdr)
Kevin O'Connora979c1c2010-03-09 20:01:35 -050046 if callinfo[0] not in seenbefore:
47 seenbefore[callinfo[0]] = 1
48 totcalls += 1 + callinfo[5]
49 funcnameroot = callinfo[0].split('.')[0]
50 if funcnameroot in IGNORE:
Kevin O'Connor95cde272008-07-13 10:59:11 -040051 # This called function is ignored - don't contribute it to
52 # the max stack.
53 continue
Kevin O'Connora979c1c2010-03-09 20:01:35 -050054 if funcnameroot in STACKHOP:
55 if usage > maxusage:
56 maxusage = usage
57 if callinfo[4] is not None:
58 doesyield = 1
59 if usage > maxyieldusage:
60 maxyieldusage = usage
61 continue
Kevin O'Connor95cde272008-07-13 10:59:11 -040062 totusage = usage + callinfo[2]
Kevin O'Connora979c1c2010-03-09 20:01:35 -050063 if totusage > maxusage:
64 maxusage = totusage
65 if callinfo[4] is not None:
66 doesyield = 1
67 totyieldusage = usage + callinfo[4]
68 if totyieldusage > maxyieldusage:
69 maxyieldusage = totyieldusage
70 info[2] = maxusage
71 if doesyield:
72 info[4] = maxyieldusage
73 info[5] = totcalls
74
75# Try to arrange output so that functions that call each other are
76# near each other.
77def orderfuncs(funcnames, availnames, funcs):
78 l = [(availnames[name][5], name)
79 for name in funcnames if name in availnames]
80 l.sort()
81 l.reverse()
82 out = []
83 while l:
84 count, name = l.pop(0)
85 if name not in availnames:
86 continue
87 callnames = [funcs[calls[1]][0] for calls in availnames[name][6]]
88 del availnames[name]
89 out = out + orderfuncs(callnames, availnames, funcs) + [name]
90 return out
91
92# Update function info with a found "yield" point.
93def noteYield(info, stackusage):
94 prevyield = info[3]
95 if prevyield is None or prevyield < stackusage:
96 info[3] = stackusage
97
98# Update function info with a found "call" point.
99def noteCall(info, subfuncs, insnaddr, calladdr, stackusage):
100 if (calladdr, stackusage) in subfuncs:
101 # Already noted a nearly identical call - ignore this one.
102 return
103 info[6].append((insnaddr, calladdr, stackusage))
104 subfuncs[(calladdr, stackusage)] = 1
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400105
106hex_s = r'[0-9a-f]+'
Kevin O'Connor95cde272008-07-13 10:59:11 -0400107re_func = re.compile(r'^(?P<funcaddr>' + hex_s + r') <(?P<func>.*)>:$')
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400108re_asm = re.compile(
Kevin O'Connor95cde272008-07-13 10:59:11 -0400109 r'^[ ]*(?P<insnaddr>' + hex_s
110 + r'):\t.*\t(addr32 )?(?P<insn>.+?)[ ]*((?P<calladdr>' + hex_s
111 + r') <(?P<ref>.*)>)?$')
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400112re_usestack = re.compile(
Kevin O'Connor0b04b782009-06-10 21:40:26 -0400113 r'^(push[f]?[lw])|(sub.* [$](?P<num>0x' + hex_s + r'),%esp)$')
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400114
115def calc():
Kevin O'Connor95cde272008-07-13 10:59:11 -0400116 # funcs[funcaddr] = [funcname, basicstackusage, maxstackusage
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500117 # , yieldusage, maxyieldusage, totalcalls
118 # , [(insnaddr, calladdr, stackusage), ...]]
119 funcs = {-1: ['<indirect>', 0, 0, None, None, 0, []]}
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400120 cur = None
121 atstart = 0
122 stackusage = 0
123
124 # Parse input lines
125 for line in sys.stdin.readlines():
126 m = re_func.match(line)
127 if m is not None:
128 # Found function
Kevin O'Connor95cde272008-07-13 10:59:11 -0400129 funcaddr = int(m.group('funcaddr'), 16)
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500130 funcs[funcaddr] = cur = [m.group('func'), 0, None, None, None, 0, []]
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400131 stackusage = 0
132 atstart = 1
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400133 subfuncs = {}
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400134 continue
135 m = re_asm.match(line)
136 if m is not None:
137 insn = m.group('insn')
138
139 im = re_usestack.match(insn)
140 if im is not None:
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400141 if insn[:5] == 'pushl' or insn[:6] == 'pushfl':
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400142 stackusage += 4
143 continue
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400144 elif insn[:5] == 'pushw' or insn[:6] == 'pushfw':
145 stackusage += 2
146 continue
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400147 stackusage += int(im.group('num'), 16)
148
149 if atstart:
Kevin O'Connordbbb7cf2009-08-09 13:10:47 -0400150 if insn == 'movl %esp,%ebp':
151 # Still part of initial header
152 continue
Kevin O'Connor95cde272008-07-13 10:59:11 -0400153 cur[1] = stackusage
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400154 atstart = 0
155
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500156 insnaddr = m.group('insnaddr')
Kevin O'Connor95cde272008-07-13 10:59:11 -0400157 calladdr = m.group('calladdr')
158 if calladdr is None:
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400159 if insn[:6] == 'lcallw':
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500160 noteCall(cur, subfuncs, insnaddr, -1, stackusage + 4)
161 noteYield(cur, stackusage + 4)
162 elif insn[:3] == 'int':
163 noteCall(cur, subfuncs, insnaddr, -1, stackusage + 6)
164 noteYield(cur, stackusage + 6)
165 elif insn[:3] == 'sti':
166 noteYield(cur, stackusage)
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400167 else:
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500168 # misc instruction
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400169 continue
170 else:
171 # Jump or call insn
Kevin O'Connor95cde272008-07-13 10:59:11 -0400172 calladdr = int(calladdr, 16)
173 ref = m.group('ref')
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400174 if '+' in ref:
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500175 # Inter-function jump.
176 pass
177 elif insn[:1] == 'j':
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400178 # Tail call
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500179 noteCall(cur, subfuncs, insnaddr, calladdr, 0)
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400180 elif insn[:5] == 'calll':
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500181 noteCall(cur, subfuncs, insnaddr, calladdr, stackusage + 4)
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400182 else:
183 print "unknown call", ref
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500184 noteCall(cur, subfuncs, insnaddr, calladdr, stackusage)
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400185 # Reset stack usage to preamble usage
Kevin O'Connor95cde272008-07-13 10:59:11 -0400186 stackusage = cur[1]
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400187
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400188 #print "other", repr(line)
189
190 # Calculate maxstackusage
Kevin O'Connor95cde272008-07-13 10:59:11 -0400191 bynames = {}
192 for funcaddr, info in funcs.items():
193 bynames[info[0]] = info
194 if info[2] is not None:
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400195 continue
Kevin O'Connor95cde272008-07-13 10:59:11 -0400196 calcmaxstack(funcs, funcaddr)
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400197
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500198 # Sort functions for output
Kevin O'Connor95cde272008-07-13 10:59:11 -0400199 funcnames = bynames.keys()
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500200 funcnames = orderfuncs(funcnames, bynames.copy(), funcs)
201
202 # Show all functions
203 print OUTPUTDESC
Kevin O'Connor95cde272008-07-13 10:59:11 -0400204 for funcname in funcnames:
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500205 name, basicusage, maxusage, yieldusage, maxyieldusage, count, calls = \
206 bynames[funcname]
207 if maxusage == 0 and maxyieldusage is None:
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400208 continue
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500209 yieldstr = ""
210 if maxyieldusage is not None:
211 yieldstr = ",%d" % maxyieldusage
212 print "\n%s[%d,%d%s]:" % (funcname, basicusage, maxusage, yieldstr)
Kevin O'Connor95cde272008-07-13 10:59:11 -0400213 for insnaddr, calladdr, stackusage in calls:
214 callinfo = funcs[calladdr]
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500215 yieldstr = ""
216 if callinfo[4] is not None:
217 yieldstr = ",%d" % (stackusage + callinfo[4])
218 print " %04s:%-40s [%d+%d,%d%s]" % (
Kevin O'Connor95cde272008-07-13 10:59:11 -0400219 insnaddr, callinfo[0], stackusage, callinfo[1]
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500220 , stackusage+callinfo[2], yieldstr)
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400221
222def main():
223 calc()
224
225if __name__ == '__main__':
226 main()