[Python-checkins] CVS: python/dist/src/Lib/compiler pyassem.py,1.27,1.28
Jeremy Hylton
jhylton@users.sourceforge.net
Wed, 17 Oct 2001 06:37:31 -0700
Update of /cvsroot/python/python/dist/src/Lib/compiler
In directory usw-pr-cvs1:/tmp/cvs-serv18531/Lib/compiler
Modified Files:
pyassem.py
Log Message:
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.
Index: pyassem.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/compiler/pyassem.py,v
retrieving revision 1.27
retrieving revision 1.28
diff -C2 -d -r1.27 -r1.28
*** pyassem.py 2001/09/14 22:49:08 1.27
--- pyassem.py 2001/10/17 13:37:29 1.28
***************
*** 197,201 ****
chains.insert(goes_before, c)
-
del blocks[:]
for c in chains:
--- 197,200 ----
***************
*** 375,378 ****
--- 374,378 ----
"""Get a Python code object"""
if self.stage == RAW:
+ self.computeStackDepth()
self.flattenGraph()
if self.stage == FLAT:
***************
*** 402,405 ****
--- 402,435 ----
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"""
***************
*** 433,437 ****
elif self.hasjabs.has_elt(opname):
insts[i] = opname, begin[inst[1]]
- self.stacksize = findDepth(self.insts)
self.stage = FLAT
--- 463,466 ----
***************
*** 694,712 ****
# XXX 2. at least partly as a result, this code is broken
! def findDepth(self, insts):
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
depth = depth + delta
else:
- if depth > maxDepth:
- maxDepth = depth
# now check patterns
for pat, pat_delta in self.patterns:
--- 723,737 ----
# XXX 2. at least partly as a result, this code is broken
! def findDepth(self, insts, debug=0):
depth = 0
maxDepth = 0
for i in insts:
opname = i[0]
! if debug:
! print i,
! delta = self.effect.get(opname, None)
! if delta is not None:
depth = depth + delta
else:
# now check patterns
for pat, pat_delta in self.patterns:
***************
*** 716,725 ****
break
# if we still haven't found a match
! if delta == 0:
meth = getattr(self, opname, None)
if meth is not None:
depth = depth + meth(i[1])
! if depth < 0:
! depth = 0
return maxDepth
--- 741,752 ----
break
# if we still haven't found a match
! if delta is None:
meth = getattr(self, opname, None)
if meth is not None:
depth = depth + meth(i[1])
! if depth > maxDepth:
! maxDepth = depth
! if debug:
! print depth, maxDepth
return maxDepth
***************
*** 755,758 ****
--- 782,786 ----
'IMPORT_NAME': 0,
'IMPORT_FROM': 1,
+ 'LOAD_ATTR': 0, # unlike other loads
# close enough...
'SETUP_EXCEPT': 3,
***************
*** 774,786 ****
def CALL_FUNCTION(self, argc):
hi, lo = divmod(argc, 256)
! return lo + hi * 2
def CALL_FUNCTION_VAR(self, argc):
! return self.CALL_FUNCTION(argc)+1
def CALL_FUNCTION_KW(self, argc):
! return self.CALL_FUNCTION(argc)+1
def CALL_FUNCTION_VAR_KW(self, argc):
! return self.CALL_FUNCTION(argc)+2
def MAKE_FUNCTION(self, argc):
return -argc
def BUILD_SLICE(self, argc):
if argc == 2:
--- 802,817 ----
def CALL_FUNCTION(self, argc):
hi, lo = divmod(argc, 256)
! return -(lo + hi * 2)
def CALL_FUNCTION_VAR(self, argc):
! return self.CALL_FUNCTION(argc)-1
def CALL_FUNCTION_KW(self, argc):
! return self.CALL_FUNCTION(argc)-1
def CALL_FUNCTION_VAR_KW(self, argc):
! 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:
***************
*** 788,791 ****
--- 819,824 ----
elif argc == 3:
return -2
+ def DUP_TOPX(self, argc):
+ return argc
findDepth = StackDepthTracker().findDepth