blob: e86a649b468a97ad69109203257d821dbefac98f [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'Connorffc06872014-06-11 15:40:04 -040010# objdump -m i386 -M i8086 -M suffix -d out/rom16.o | scripts/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
Kevin O'Connorecdc6552012-05-28 14:25:15 -040016STACKHOP = ['stack_hop', 'stack_hop_back']
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'Connorf59b5ac2010-05-01 11:03:10 -040043 callinfo = funcs.get(calladdr)
44 if callinfo is None:
45 continue
Kevin O'Connor95cde272008-07-13 10:59:11 -040046 if callinfo[2] is None:
47 calcmaxstack(funcs, calladdr)
Kevin O'Connora979c1c2010-03-09 20:01:35 -050048 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:
Kevin O'Connor95cde272008-07-13 10:59:11 -040053 # This called function is ignored - don't contribute it to
54 # the max stack.
55 continue
Kevin O'Connora979c1c2010-03-09 20:01:35 -050056 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
Kevin O'Connor95cde272008-07-13 10:59:11 -040064 totusage = usage + callinfo[2]
Kevin O'Connora979c1c2010-03-09 20:01:35 -050065 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.
Kevin O'Connorf59b5ac2010-05-01 11:03:10 -040079def orderfuncs(funcaddrs, availfuncs):
80 l = [(availfuncs[funcaddr][5], availfuncs[funcaddr][0], funcaddr)
81 for funcaddr in funcaddrs if funcaddr in availfuncs]
Kevin O'Connora979c1c2010-03-09 20:01:35 -050082 l.sort()
83 l.reverse()
84 out = []
85 while l:
Kevin O'Connorf59b5ac2010-05-01 11:03:10 -040086 count, name, funcaddr = l.pop(0)
87 if funcaddr not in availfuncs:
Kevin O'Connora979c1c2010-03-09 20:01:35 -050088 continue
Kevin O'Connorf59b5ac2010-05-01 11:03:10 -040089 calladdrs = [calls[1] for calls in availfuncs[funcaddr][6]]
90 del availfuncs[funcaddr]
91 out = out + orderfuncs(calladdrs, availfuncs) + [funcaddr]
Kevin O'Connora979c1c2010-03-09 20:01:35 -050092 return out
93
94# Update function info with a found "yield" point.
95def 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.
101def 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
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400107
108hex_s = r'[0-9a-f]+'
Kevin O'Connor95cde272008-07-13 10:59:11 -0400109re_func = re.compile(r'^(?P<funcaddr>' + hex_s + r') <(?P<func>.*)>:$')
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400110re_asm = re.compile(
Kevin O'Connor95cde272008-07-13 10:59:11 -0400111 r'^[ ]*(?P<insnaddr>' + hex_s
112 + r'):\t.*\t(addr32 )?(?P<insn>.+?)[ ]*((?P<calladdr>' + hex_s
113 + r') <(?P<ref>.*)>)?$')
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400114re_usestack = re.compile(
Kevin O'Connor0b04b782009-06-10 21:40:26 -0400115 r'^(push[f]?[lw])|(sub.* [$](?P<num>0x' + hex_s + r'),%esp)$')
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400116
117def calc():
Kevin O'Connor95cde272008-07-13 10:59:11 -0400118 # funcs[funcaddr] = [funcname, basicstackusage, maxstackusage
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500119 # , yieldusage, maxyieldusage, totalcalls
120 # , [(insnaddr, calladdr, stackusage), ...]]
121 funcs = {-1: ['<indirect>', 0, 0, None, None, 0, []]}
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400122 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
Kevin O'Connor95cde272008-07-13 10:59:11 -0400131 funcaddr = int(m.group('funcaddr'), 16)
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500132 funcs[funcaddr] = cur = [m.group('func'), 0, None, None, None, 0, []]
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400133 stackusage = 0
134 atstart = 1
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400135 subfuncs = {}
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400136 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:
Kevin O'Connor6c2e7812010-09-13 18:04:02 -0400143 if insn.startswith('pushl') or insn.startswith('pushfl'):
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400144 stackusage += 4
145 continue
Kevin O'Connor6c2e7812010-09-13 18:04:02 -0400146 elif insn.startswith('pushw') or insn.startswith('pushfw'):
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400147 stackusage += 2
148 continue
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400149 stackusage += int(im.group('num'), 16)
150
151 if atstart:
Kevin O'Connor6ee837b2012-02-13 20:09:02 -0500152 if '%esp' in insn or insn.startswith('leal'):
Kevin O'Connordbbb7cf2009-08-09 13:10:47 -0400153 # Still part of initial header
154 continue
Kevin O'Connor95cde272008-07-13 10:59:11 -0400155 cur[1] = stackusage
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400156 atstart = 0
157
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500158 insnaddr = m.group('insnaddr')
Kevin O'Connor95cde272008-07-13 10:59:11 -0400159 calladdr = m.group('calladdr')
160 if calladdr is None:
Kevin O'Connor6c2e7812010-09-13 18:04:02 -0400161 if insn.startswith('lcallw'):
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500162 noteCall(cur, subfuncs, insnaddr, -1, stackusage + 4)
163 noteYield(cur, stackusage + 4)
Kevin O'Connor6c2e7812010-09-13 18:04:02 -0400164 elif insn.startswith('int'):
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500165 noteCall(cur, subfuncs, insnaddr, -1, stackusage + 6)
166 noteYield(cur, stackusage + 6)
Kevin O'Connor6c2e7812010-09-13 18:04:02 -0400167 elif insn.startswith('sti'):
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500168 noteYield(cur, stackusage)
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400169 else:
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500170 # misc instruction
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400171 continue
172 else:
173 # Jump or call insn
Kevin O'Connor95cde272008-07-13 10:59:11 -0400174 calladdr = int(calladdr, 16)
175 ref = m.group('ref')
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400176 if '+' in ref:
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500177 # Inter-function jump.
178 pass
Kevin O'Connor6c2e7812010-09-13 18:04:02 -0400179 elif insn.startswith('j'):
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400180 # Tail call
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500181 noteCall(cur, subfuncs, insnaddr, calladdr, 0)
Kevin O'Connor6c2e7812010-09-13 18:04:02 -0400182 elif insn.startswith('calll'):
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500183 noteCall(cur, subfuncs, insnaddr, calladdr, stackusage + 4)
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400184 else:
Johannes Krampf064fd062014-01-12 11:14:54 -0500185 print("unknown call", ref)
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500186 noteCall(cur, subfuncs, insnaddr, calladdr, stackusage)
Kevin O'Connorf5cb0792008-06-07 10:11:36 -0400187 # Reset stack usage to preamble usage
Kevin O'Connor95cde272008-07-13 10:59:11 -0400188 stackusage = cur[1]
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400189
Johannes Krampf064fd062014-01-12 11:14:54 -0500190 #print("other", repr(line))
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400191
192 # Calculate maxstackusage
Kevin O'Connor95cde272008-07-13 10:59:11 -0400193 for funcaddr, info in funcs.items():
Kevin O'Connor95cde272008-07-13 10:59:11 -0400194 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'Connorf59b5ac2010-05-01 11:03:10 -0400199 funcaddrs = orderfuncs(funcs.keys(), funcs.copy())
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500200
201 # Show all functions
Johannes Krampf064fd062014-01-12 11:14:54 -0500202 print(OUTPUTDESC)
Kevin O'Connorf59b5ac2010-05-01 11:03:10 -0400203 for funcaddr in funcaddrs:
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500204 name, basicusage, maxusage, yieldusage, maxyieldusage, count, calls = \
Kevin O'Connorf59b5ac2010-05-01 11:03:10 -0400205 funcs[funcaddr]
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500206 if maxusage == 0 and maxyieldusage is None:
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400207 continue
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500208 yieldstr = ""
209 if maxyieldusage is not None:
210 yieldstr = ",%d" % maxyieldusage
Johannes Krampf064fd062014-01-12 11:14:54 -0500211 print("\n%s[%d,%d%s]:" % (name, basicusage, maxusage, yieldstr))
Kevin O'Connor95cde272008-07-13 10:59:11 -0400212 for insnaddr, calladdr, stackusage in calls:
Kevin O'Connorf59b5ac2010-05-01 11:03:10 -0400213 callinfo = funcs.get(calladdr, ("<unknown>", 0, 0, 0, None))
Kevin O'Connora979c1c2010-03-09 20:01:35 -0500214 yieldstr = ""
215 if callinfo[4] is not None:
216 yieldstr = ",%d" % (stackusage + callinfo[4])
Johannes Krampf064fd062014-01-12 11:14:54 -0500217 print(" %04s:%-40s [%d+%d,%d%s]" % (
Kevin O'Connor95cde272008-07-13 10:59:11 -0400218 insnaddr, callinfo[0], stackusage, callinfo[1]
Johannes Krampf064fd062014-01-12 11:14:54 -0500219 , stackusage+callinfo[2], yieldstr))
Kevin O'Connor5c4a8c62008-05-12 23:50:16 -0400220
221def main():
222 calc()
223
224if __name__ == '__main__':
225 main()