The checkstack.py script (which tries to estimate the stack usage of generated C code) was in need of a little cleanup. I actually wanted to use the script in another project and so needed to clean it up. I think it's worthwhile to push the changes back into the repo though. There should be no functional changes in this series.
-Kevin
Kevin O'Connor (3): checkstack: Replace function information tuple with class checkstack: Simplify yield calculations checkstack: Prefer passing "function" class instead of function address
scripts/checkstack.py | 184 ++++++++++++++++++++++++-------------------------- 1 file changed, 89 insertions(+), 95 deletions(-)
Replace the six-tuple storing information on each parsed function with a class. This makes the code more readable.
Signed-off-by: Kevin O'Connor kevin@koconnor.net --- scripts/checkstack.py | 146 ++++++++++++++++++++++++++------------------------ 1 file changed, 77 insertions(+), 69 deletions(-)
diff --git a/scripts/checkstack.py b/scripts/checkstack.py index b49b6c8..f13a7bc 100755 --- a/scripts/checkstack.py +++ b/scripts/checkstack.py @@ -2,7 +2,7 @@ # Script that tries to find how much stack space each function in an # object is using. # -# Copyright (C) 2008 Kevin O'Connor kevin@koconnor.net +# Copyright (C) 2008-2015 Kevin O'Connor kevin@koconnor.net # # This file may be distributed under the terms of the GNU GPLv3 license.
@@ -26,29 +26,53 @@ OUTPUTDESC = """ # insn_addr:called_function [u+c,t,usage_to_yield_point] """
+class function: + def __init__(self, funcaddr, funcname): + self.funcaddr = funcaddr + self.funcname = funcname + self.basic_stack_usage = 0 + self.max_stack_usage = None + self.yield_usage = None + self.max_yield_usage = None + self.total_calls = 0 + # called_funcs = [(insnaddr, calladdr, stackusage), ...] + self.called_funcs = [] + self.subfuncs = {} + # Update function info with a found "yield" point. + def noteYield(self, stackusage): + if self.yield_usage is None or self.yield_usage < stackusage: + self.yield_usage = stackusage + # Update function info with a found "call" point. + def noteCall(self, insnaddr, calladdr, stackusage): + if (calladdr, stackusage) in self.subfuncs: + # Already noted a nearly identical call - ignore this one. + return + self.called_funcs.append((insnaddr, calladdr, stackusage)) + self.subfuncs[(calladdr, stackusage)] = 1 + # Find out maximum stack usage for a function def calcmaxstack(funcs, funcaddr): info = funcs[funcaddr] # Find max of all nested calls. - maxusage = info[1] + maxusage = info.basic_stack_usage maxyieldusage = doesyield = 0 - if info[3] is not None: - maxyieldusage = info[3] + if info.yield_usage is not None: + maxyieldusage = info.yield_usage doesyield = 1 - info[2] = maxusage - info[4] = info[3] + info.max_stack_usage = maxusage + info.max_yield_usage = info.yield_usage seenbefore = {} totcalls = 0 - for insnaddr, calladdr, usage in info[6]: + for insnaddr, calladdr, usage in info.called_funcs: callinfo = funcs.get(calladdr) if callinfo is None: continue - if callinfo[2] is None: + if callinfo.max_stack_usage is None: calcmaxstack(funcs, calladdr) - if callinfo[0] not in seenbefore: - seenbefore[callinfo[0]] = 1 - totcalls += 1 + callinfo[5] - funcnameroot = callinfo[0].split('.')[0] + if callinfo.funcname not in seenbefore: + seenbefore[callinfo.funcname] = 1 + totcalls += 1 + callinfo.total_calls + funcnameroot = callinfo.funcname.split('.')[0] if funcnameroot in IGNORE: # This called function is ignored - don't contribute it to # the max stack. @@ -56,28 +80,29 @@ def calcmaxstack(funcs, funcaddr): if funcnameroot in STACKHOP: if usage > maxusage: maxusage = usage - if callinfo[4] is not None: + if callinfo.max_yield_usage is not None: doesyield = 1 if usage > maxyieldusage: maxyieldusage = usage continue - totusage = usage + callinfo[2] + totusage = usage + callinfo.max_stack_usage if totusage > maxusage: maxusage = totusage - if callinfo[4] is not None: + if callinfo.max_yield_usage is not None: doesyield = 1 - totyieldusage = usage + callinfo[4] + totyieldusage = usage + callinfo.max_yield_usage if totyieldusage > maxyieldusage: maxyieldusage = totyieldusage - info[2] = maxusage + info.max_stack_usage = maxusage if doesyield: - info[4] = maxyieldusage - info[5] = totcalls + info.max_yield_usage = maxyieldusage + info.total_calls = totcalls
# Try to arrange output so that functions that call each other are # near each other. def orderfuncs(funcaddrs, availfuncs): - l = [(availfuncs[funcaddr][5], availfuncs[funcaddr][0], funcaddr) + l = [(availfuncs[funcaddr].total_calls + , availfuncs[funcaddr].funcname, funcaddr) for funcaddr in funcaddrs if funcaddr in availfuncs] l.sort() l.reverse() @@ -86,25 +111,11 @@ def orderfuncs(funcaddrs, availfuncs): count, name, funcaddr = l.pop(0) if funcaddr not in availfuncs: continue - calladdrs = [calls[1] for calls in availfuncs[funcaddr][6]] + calladdrs = [calls[1] for calls in availfuncs[funcaddr].called_funcs] del availfuncs[funcaddr] out = out + orderfuncs(calladdrs, availfuncs) + [funcaddr] return out
-# Update function info with a found "yield" point. -def noteYield(info, stackusage): - prevyield = info[3] - if prevyield is None or prevyield < stackusage: - info[3] = stackusage - -# Update function info with a found "call" point. -def noteCall(info, subfuncs, insnaddr, calladdr, stackusage): - if (calladdr, stackusage) in subfuncs: - # Already noted a nearly identical call - ignore this one. - return - info[6].append((insnaddr, calladdr, stackusage)) - subfuncs[(calladdr, stackusage)] = 1 - hex_s = r'[0-9a-f]+' re_func = re.compile(r'^(?P<funcaddr>' + hex_s + r') <(?P<func>.*)>:$') re_asm = re.compile( @@ -114,11 +125,11 @@ re_asm = re.compile( re_usestack = re.compile( r'^(push[f]?[lw])|(sub.* [$](?P<num>0x' + hex_s + r'),%esp)$')
-def calc(): - # funcs[funcaddr] = [funcname, basicstackusage, maxstackusage - # , yieldusage, maxyieldusage, totalcalls - # , [(insnaddr, calladdr, stackusage), ...]] - funcs = {-1: ['<indirect>', 0, 0, None, None, 0, []]} +def main(): + unknownfunc = function(None, "<unknown>") + indirectfunc = function(-1, '<indirect>') + unknownfunc.max_stack_usage = indirectfunc.max_stack_usage = 0 + funcs = {-1: indirectfunc} cur = None atstart = 0 stackusage = 0 @@ -129,10 +140,9 @@ def calc(): if m is not None: # Found function funcaddr = int(m.group('funcaddr'), 16) - funcs[funcaddr] = cur = [m.group('func'), 0, None, None, None, 0, []] + funcs[funcaddr] = cur = function(funcaddr, m.group('func')) stackusage = 0 atstart = 1 - subfuncs = {} continue m = re_asm.match(line) if m is not None: @@ -152,20 +162,20 @@ def calc(): if '%esp' in insn or insn.startswith('leal'): # Still part of initial header continue - cur[1] = stackusage + cur.basic_stack_usage = stackusage atstart = 0
insnaddr = m.group('insnaddr') calladdr = m.group('calladdr') if calladdr is None: if insn.startswith('lcallw'): - noteCall(cur, subfuncs, insnaddr, -1, stackusage + 4) - noteYield(cur, stackusage + 4) + cur.noteCall(insnaddr, -1, stackusage + 4) + cur.noteYield(stackusage + 4) elif insn.startswith('int'): - noteCall(cur, subfuncs, insnaddr, -1, stackusage + 6) - noteYield(cur, stackusage + 6) + cur.noteCall(insnaddr, -1, stackusage + 6) + cur.noteYield(stackusage + 6) elif insn.startswith('sti'): - noteYield(cur, stackusage) + cur.noteYield(stackusage) else: # misc instruction continue @@ -178,22 +188,22 @@ def calc(): pass elif insn.startswith('j'): # Tail call - noteCall(cur, subfuncs, insnaddr, calladdr, 0) + cur.noteCall(insnaddr, calladdr, 0) elif insn.startswith('calll'): - noteCall(cur, subfuncs, insnaddr, calladdr, stackusage + 4) + cur.noteCall(insnaddr, calladdr, stackusage + 4) elif insn.startswith('callw'): - noteCall(cur, subfuncs, insnaddr, calladdr, stackusage + 2) + cur.noteCall(insnaddr, calladdr, stackusage + 2) else: print("unknown call", ref) - noteCall(cur, subfuncs, insnaddr, calladdr, stackusage) + cur.noteCall(insnaddr, calladdr, stackusage) # Reset stack usage to preamble usage - stackusage = cur[1] + stackusage = cur.basic_stack_usage
#print("other", repr(line))
# Calculate maxstackusage for funcaddr, info in funcs.items(): - if info[2] is not None: + if info.max_stack_usage is not None: continue calcmaxstack(funcs, funcaddr)
@@ -203,25 +213,23 @@ def calc(): # Show all functions print(OUTPUTDESC) for funcaddr in funcaddrs: - name, basicusage, maxusage, yieldusage, maxyieldusage, count, calls = \ - funcs[funcaddr] - if maxusage == 0 and maxyieldusage is None: + info = funcs[funcaddr] + if info.max_stack_usage == 0 and info.max_yield_usage is None: continue yieldstr = "" - if maxyieldusage is not None: - yieldstr = ",%d" % maxyieldusage - print("\n%s[%d,%d%s]:" % (name, basicusage, maxusage, yieldstr)) - for insnaddr, calladdr, stackusage in calls: - callinfo = funcs.get(calladdr, ("<unknown>", 0, 0, 0, None)) + if info.max_yield_usage is not None: + yieldstr = ",%d" % info.max_yield_usage + print("\n%s[%d,%d%s]:" % (info.funcname, info.basic_stack_usage + , info.max_stack_usage, yieldstr)) + for insnaddr, calladdr, stackusage in info.called_funcs: + callinfo = funcs.get(calladdr, unknownfunc) yieldstr = "" - if callinfo[4] is not None: - yieldstr = ",%d" % (stackusage + callinfo[4]) + if callinfo.max_yield_usage is not None: + yieldstr = ",%d" % (stackusage + callinfo.max_yield_usage) print(" %04s:%-40s [%d+%d,%d%s]" % ( - insnaddr, callinfo[0], stackusage, callinfo[1] - , stackusage+callinfo[2], yieldstr)) - -def main(): - calc() + insnaddr, callinfo.funcname, stackusage + , callinfo.basic_stack_usage + , stackusage+callinfo.max_stack_usage, yieldstr))
if __name__ == '__main__': main()
Signed-off-by: Kevin O'Connor kevin@koconnor.net --- scripts/checkstack.py | 54 ++++++++++++++++++++------------------------------- 1 file changed, 21 insertions(+), 33 deletions(-)
diff --git a/scripts/checkstack.py b/scripts/checkstack.py index f13a7bc..6b3c80a 100755 --- a/scripts/checkstack.py +++ b/scripts/checkstack.py @@ -32,7 +32,7 @@ class function: self.funcname = funcname self.basic_stack_usage = 0 self.max_stack_usage = None - self.yield_usage = None + self.yield_usage = -1 self.max_yield_usage = None self.total_calls = 0 # called_funcs = [(insnaddr, calladdr, stackusage), ...] @@ -40,7 +40,7 @@ class function: self.subfuncs = {} # Update function info with a found "yield" point. def noteYield(self, stackusage): - if self.yield_usage is None or self.yield_usage < stackusage: + if self.yield_usage < stackusage: self.yield_usage = stackusage # Update function info with a found "call" point. def noteCall(self, insnaddr, calladdr, stackusage): @@ -54,15 +54,10 @@ class function: def calcmaxstack(funcs, funcaddr): info = funcs[funcaddr] # Find max of all nested calls. - maxusage = info.basic_stack_usage - maxyieldusage = doesyield = 0 - if info.yield_usage is not None: - maxyieldusage = info.yield_usage - doesyield = 1 - info.max_stack_usage = maxusage - info.max_yield_usage = info.yield_usage + info.max_stack_usage = max_stack_usage = info.basic_stack_usage + info.max_yield_usage = max_yield_usage = info.yield_usage + total_calls = 0 seenbefore = {} - totcalls = 0 for insnaddr, calladdr, usage in info.called_funcs: callinfo = funcs.get(calladdr) if callinfo is None: @@ -71,32 +66,24 @@ def calcmaxstack(funcs, funcaddr): calcmaxstack(funcs, calladdr) if callinfo.funcname not in seenbefore: seenbefore[callinfo.funcname] = 1 - totcalls += 1 + callinfo.total_calls + total_calls += callinfo.total_calls + 1 funcnameroot = callinfo.funcname.split('.')[0] if funcnameroot in IGNORE: # This called function is ignored - don't contribute it to # the max stack. continue - if funcnameroot in STACKHOP: - if usage > maxusage: - maxusage = usage - if callinfo.max_yield_usage is not None: - doesyield = 1 - if usage > maxyieldusage: - maxyieldusage = usage - continue totusage = usage + callinfo.max_stack_usage - if totusage > maxusage: - maxusage = totusage - if callinfo.max_yield_usage is not None: - doesyield = 1 - totyieldusage = usage + callinfo.max_yield_usage - if totyieldusage > maxyieldusage: - maxyieldusage = totyieldusage - info.max_stack_usage = maxusage - if doesyield: - info.max_yield_usage = maxyieldusage - info.total_calls = totcalls + totyieldusage = usage + callinfo.max_yield_usage + if funcnameroot in STACKHOP: + # Don't count children of this function + totusage = totyieldusage = usage + if totusage > max_stack_usage: + max_stack_usage = totusage + if callinfo.max_yield_usage >= 0 and totyieldusage > max_yield_usage: + max_yield_usage = totyieldusage + info.max_stack_usage = max_stack_usage + info.max_yield_usage = max_yield_usage + info.total_calls = total_calls
# Try to arrange output so that functions that call each other are # near each other. @@ -129,6 +116,7 @@ def main(): unknownfunc = function(None, "<unknown>") indirectfunc = function(-1, '<indirect>') unknownfunc.max_stack_usage = indirectfunc.max_stack_usage = 0 + unknownfunc.max_yield_usage = indirectfunc.max_yield_usage = -1 funcs = {-1: indirectfunc} cur = None atstart = 0 @@ -214,17 +202,17 @@ def main(): print(OUTPUTDESC) for funcaddr in funcaddrs: info = funcs[funcaddr] - if info.max_stack_usage == 0 and info.max_yield_usage is None: + if info.max_stack_usage == 0 and info.max_yield_usage < 0: continue yieldstr = "" - if info.max_yield_usage is not None: + if info.max_yield_usage >= 0: yieldstr = ",%d" % info.max_yield_usage print("\n%s[%d,%d%s]:" % (info.funcname, info.basic_stack_usage , info.max_stack_usage, yieldstr)) for insnaddr, calladdr, stackusage in info.called_funcs: callinfo = funcs.get(calladdr, unknownfunc) yieldstr = "" - if callinfo.max_yield_usage is not None: + if callinfo.max_yield_usage >= 0: yieldstr = ",%d" % (stackusage + callinfo.max_yield_usage) print(" %04s:%-40s [%d+%d,%d%s]" % ( insnaddr, callinfo.funcname, stackusage
Signed-off-by: Kevin O'Connor kevin@koconnor.net --- scripts/checkstack.py | 28 +++++++++++++--------------- 1 file changed, 13 insertions(+), 15 deletions(-)
diff --git a/scripts/checkstack.py b/scripts/checkstack.py index 6b3c80a..d7fc30c 100755 --- a/scripts/checkstack.py +++ b/scripts/checkstack.py @@ -51,19 +51,19 @@ class function: self.subfuncs[(calladdr, stackusage)] = 1
# Find out maximum stack usage for a function -def calcmaxstack(funcs, funcaddr): - info = funcs[funcaddr] - # Find max of all nested calls. +def calcmaxstack(info, funcs): + if info.max_stack_usage is not None: + return info.max_stack_usage = max_stack_usage = info.basic_stack_usage info.max_yield_usage = max_yield_usage = info.yield_usage total_calls = 0 seenbefore = {} + # Find max of all nested calls. for insnaddr, calladdr, usage in info.called_funcs: callinfo = funcs.get(calladdr) if callinfo is None: continue - if callinfo.max_stack_usage is None: - calcmaxstack(funcs, calladdr) + calcmaxstack(callinfo, funcs) if callinfo.funcname not in seenbefore: seenbefore[callinfo.funcname] = 1 total_calls += callinfo.total_calls + 1 @@ -96,11 +96,12 @@ def orderfuncs(funcaddrs, availfuncs): out = [] while l: count, name, funcaddr = l.pop(0) - if funcaddr not in availfuncs: + info = availfuncs.get(funcaddr) + if info is None: continue - calladdrs = [calls[1] for calls in availfuncs[funcaddr].called_funcs] + calladdrs = [calls[1] for calls in info.called_funcs] del availfuncs[funcaddr] - out = out + orderfuncs(calladdrs, availfuncs) + [funcaddr] + out = out + orderfuncs(calladdrs, availfuncs) + [info] return out
hex_s = r'[0-9a-f]+' @@ -190,18 +191,15 @@ def main(): #print("other", repr(line))
# Calculate maxstackusage - for funcaddr, info in funcs.items(): - if info.max_stack_usage is not None: - continue - calcmaxstack(funcs, funcaddr) + for info in funcs.values(): + calcmaxstack(info, funcs)
# Sort functions for output - funcaddrs = orderfuncs(funcs.keys(), funcs.copy()) + funcinfos = orderfuncs(funcs.keys(), funcs.copy())
# Show all functions print(OUTPUTDESC) - for funcaddr in funcaddrs: - info = funcs[funcaddr] + for info in funcinfos: if info.max_stack_usage == 0 and info.max_yield_usage < 0: continue yieldstr = ""
On Fri, Mar 20, 2015 at 08:30:54PM -0400, Kevin O'Connor wrote:
The checkstack.py script (which tries to estimate the stack usage of generated C code) was in need of a little cleanup. I actually wanted to use the script in another project and so needed to clean it up. I think it's worthwhile to push the changes back into the repo though. There should be no functional changes in this series.
FYI, I pushed this series to the main repo.
-Kevin
-
Kevin O'Connor