summaryrefslogtreecommitdiffstats
path: root/Lib/compiler
diff options
context:
space:
mode:
authorJeremy Hylton <jeremy@alum.mit.edu>2001-10-17 13:37:29 (GMT)
committerJeremy Hylton <jeremy@alum.mit.edu>2001-10-17 13:37:29 (GMT)
commit138d90eb73415e48a0e7f09a7c9603b1164bcaed (patch)
treeb631166b29128e07e71b263e145634a6870c47a8 /Lib/compiler
parentd114261608f986b5c797eef4330fbe32041d3eb6 (diff)
downloadcpython-138d90eb73415e48a0e7f09a7c9603b1164bcaed.zip
cpython-138d90eb73415e48a0e7f09a7c9603b1164bcaed.tar.gz
cpython-138d90eb73415e48a0e7f09a7c9603b1164bcaed.tar.bz2
Vastly improved stacksize calculation.
There are now no known cases where the compiler package computes a stack depth lower than the one computed by the builtin compiler. (To achieve this state, we had to fix bugs in both compilers :-). The chief change is to do the depth calculations with respect to basic blocks. The stack effect of block is calculated. Then the flow graph is traversed using breadth-first search to find the max weight path through the graph. Had to fix the StackDepthTracker to calculate the right info for several opcodes: LOAD_ATTR, CALL_FUNCTION (and friends), MAKE_CLOSURE, and DUP_TOPX. XXX Still need to handle free variables in MAKE_CLOSURE. XXX There are still a lot of places where the computed stack depth is larger than for the builtin compiler. These won't cause the interpreter to overflow the frame, but they waste space.
Diffstat (limited to 'Lib/compiler')
-rw-r--r--Lib/compiler/pyassem.py69
1 files changed, 51 insertions, 18 deletions
diff --git a/Lib/compiler/pyassem.py b/Lib/compiler/pyassem.py
index d9d294b..cc2d108 100644
--- a/Lib/compiler/pyassem.py
+++ b/Lib/compiler/pyassem.py
@@ -196,7 +196,6 @@ class FlowGraph:
chains.remove(c)
chains.insert(goes_before, c)
-
del blocks[:]
for c in chains:
for b in c:
@@ -374,6 +373,7 @@ class PyFlowGraph(FlowGraph):
def getCode(self):
"""Get a Python code object"""
if self.stage == RAW:
+ self.computeStackDepth()
self.flattenGraph()
if self.stage == FLAT:
self.convertArgs()
@@ -401,6 +401,36 @@ class PyFlowGraph(FlowGraph):
if io:
sys.stdout = save
+ def computeStackDepth(self):
+ """Compute the max stack depth.
+
+ Approach is to compute the stack effect of each basic block.
+ Then find the path through the code with the largest total
+ effect.
+ """
+ depth = {}
+ exit = None
+ for b in self.getBlocks():
+ depth[b] = findDepth(b.getInstructions())
+
+ seen = {}
+
+ def max_depth(b, d):
+ if seen.has_key(b):
+ return d
+ seen[b] = 1
+ d = d + depth[b]
+ children = b.get_children()
+ if children:
+ return max([max_depth(c, d) for c in children])
+ else:
+ if not b.label == "exit":
+ return max_depth(self.exit, d)
+ else:
+ return d
+
+ self.stacksize = max_depth(self.entry, 0)
+
def flattenGraph(self):
"""Arrange the blocks in order and resolve jumps"""
assert self.stage == RAW
@@ -432,7 +462,6 @@ class PyFlowGraph(FlowGraph):
insts[i] = opname, offset
elif self.hasjabs.has_elt(opname):
insts[i] = opname, begin[inst[1]]
- self.stacksize = findDepth(self.insts)
self.stage = FLAT
hasjrel = misc.Set()
@@ -693,21 +722,17 @@ class StackDepthTracker:
# XXX 1. need to keep track of stack depth on jumps
# XXX 2. at least partly as a result, this code is broken
- def findDepth(self, insts):
+ def findDepth(self, insts, debug=0):
depth = 0
maxDepth = 0
for i in insts:
opname = i[0]
- delta = self.effect.get(opname, 0)
- if delta > 1:
- depth = depth + delta
- elif delta < 0:
- if depth > maxDepth:
- maxDepth = depth
+ if debug:
+ print i,
+ delta = self.effect.get(opname, None)
+ if delta is not None:
depth = depth + delta
else:
- if depth > maxDepth:
- maxDepth = depth
# now check patterns
for pat, pat_delta in self.patterns:
if opname[:len(pat)] == pat:
@@ -715,12 +740,14 @@ class StackDepthTracker:
depth = depth + delta
break
# if we still haven't found a match
- if delta == 0:
+ if delta is None:
meth = getattr(self, opname, None)
if meth is not None:
depth = depth + meth(i[1])
- if depth < 0:
- depth = 0
+ if depth > maxDepth:
+ maxDepth = depth
+ if debug:
+ print depth, maxDepth
return maxDepth
effect = {
@@ -754,6 +781,7 @@ class StackDepthTracker:
'IMPORT_STAR': -1,
'IMPORT_NAME': 0,
'IMPORT_FROM': 1,
+ 'LOAD_ATTR': 0, # unlike other loads
# close enough...
'SETUP_EXCEPT': 3,
'SETUP_FINALLY': 3,
@@ -773,19 +801,24 @@ class StackDepthTracker:
return -count+1
def CALL_FUNCTION(self, argc):
hi, lo = divmod(argc, 256)
- return lo + hi * 2
+ return -(lo + hi * 2)
def CALL_FUNCTION_VAR(self, argc):
- return self.CALL_FUNCTION(argc)+1
+ return self.CALL_FUNCTION(argc)-1
def CALL_FUNCTION_KW(self, argc):
- return self.CALL_FUNCTION(argc)+1
+ return self.CALL_FUNCTION(argc)-1
def CALL_FUNCTION_VAR_KW(self, argc):
- return self.CALL_FUNCTION(argc)+2
+ return self.CALL_FUNCTION(argc)-2
def MAKE_FUNCTION(self, argc):
return -argc
+ def MAKE_CLOSURE(self, argc):
+ # XXX need to account for free variables too!
+ return -argc
def BUILD_SLICE(self, argc):
if argc == 2:
return -1
elif argc == 3:
return -2
+ def DUP_TOPX(self, argc):
+ return argc
findDepth = StackDepthTracker().findDepth