summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJeremy Hylton <jeremy@alum.mit.edu>2001-04-12 20:21:39 (GMT)
committerJeremy Hylton <jeremy@alum.mit.edu>2001-04-12 20:21:39 (GMT)
commit542b11acfd5309438ed2769be1fc476b9597f1fb (patch)
treea6ed2a4207c9421d884b6a171f988cb1ae2b3d8e
parent35cf0a3f90de8f2e3597e67701d1e03dd11a8cbe (diff)
downloadcpython-542b11acfd5309438ed2769be1fc476b9597f1fb.zip
cpython-542b11acfd5309438ed2769be1fc476b9597f1fb.tar.gz
cpython-542b11acfd5309438ed2769be1fc476b9597f1fb.tar.bz2
pyassem.py:
Fix annoying bugs in flow graph layout code. In some cases the implicit control transfers weren't honored. In other cases, JUMP_FORWARD instructions jumped backwards. Remove unused arg from nextBlock(). pycodegen.py Add optional force kwarg to set_lineno() that will emit a SET_LINENO even if it is the same as the previous lineno. Use explicit LOAD_FAST and STORE_FAST to access list comp implicit variables. (The symbol table doesn't know about them.)
-rw-r--r--Lib/compiler/pyassem.py101
-rw-r--r--Lib/compiler/pycodegen.py24
-rw-r--r--Tools/compiler/compiler/pyassem.py101
-rw-r--r--Tools/compiler/compiler/pycodegen.py24
4 files changed, 222 insertions, 28 deletions
diff --git a/Lib/compiler/pyassem.py b/Lib/compiler/pyassem.py
index 15e91f4..e8810ae 100644
--- a/Lib/compiler/pyassem.py
+++ b/Lib/compiler/pyassem.py
@@ -27,11 +27,12 @@ class FlowGraph:
if self._debug:
if self.current:
print "end", repr(self.current)
+ print " next", self.current.next
print " ", self.current.get_children()
print repr(block)
self.current = block
- def nextBlock(self, block=None, force=0):
+ def nextBlock(self, block=None):
# XXX think we need to specify when there is implicit transfer
# from one block to the next. might be better to represent this
# with explicit JUMP_ABSOLUTE instructions that are optimized
@@ -95,12 +96,110 @@ class FlowGraph:
b.addNext(self.exit)
order = dfs_postorder(self.entry, {})
order.reverse()
+ self.fixupOrder(order, self.exit)
# hack alert
if not self.exit in order:
order.append(self.exit)
return order
+ def fixupOrder(self, blocks, default_next):
+ """Fixup bad order introduced by DFS."""
+
+ # XXX This is a total mess. There must be a better way to get
+ # the code blocks in the right order.
+
+ self.fixupOrderHonorNext(blocks, default_next)
+ self.fixupOrderForward(blocks, default_next)
+
+ def fixupOrderHonorNext(self, blocks, default_next):
+ """Fix one problem with DFS.
+
+ The DFS uses child block, but doesn't know about the special
+ "next" block. As a result, the DFS can order blocks so that a
+ block isn't next to the right block for implicit control
+ transfers.
+ """
+ index = {}
+ for i in range(len(blocks)):
+ index[blocks[i]] = i
+
+ for i in range(0, len(blocks) - 1):
+ b = blocks[i]
+ n = blocks[i + 1]
+ if not b.next or b.next[0] == default_next or b.next[0] == n:
+ continue
+ # The blocks are in the wrong order. Find the chain of
+ # blocks to insert where they belong.
+ cur = b
+ chain = []
+ elt = cur
+ while elt.next and elt.next[0] != default_next:
+ chain.append(elt.next[0])
+ elt = elt.next[0]
+ # Now remove the blocks in the chain from the current
+ # block list, so that they can be re-inserted.
+ l = []
+ for b in chain:
+ assert index[b] > i
+ l.append((index[b], b))
+ l.sort()
+ l.reverse()
+ for j, b in l:
+ del blocks[index[b]]
+ # Insert the chain in the proper location
+ blocks[i:i + 1] = [cur] + chain
+ # Finally, re-compute the block indexes
+ for i in range(len(blocks)):
+ index[blocks[i]] = i
+
+ def fixupOrderForward(self, blocks, default_next):
+ """Make sure all JUMP_FORWARDs jump forward"""
+ index = {}
+ chains = []
+ cur = []
+ for b in blocks:
+ index[b] = len(chains)
+ cur.append(b)
+ if b.next and b.next[0] == default_next:
+ chains.append(cur)
+ cur = []
+ chains.append(cur)
+
+ while 1:
+ constraints = []
+
+ for i in range(len(chains)):
+ l = chains[i]
+ for b in l:
+ for c in b.get_children():
+ if index[c] < i:
+ forward_p = 0
+ for inst in b.insts:
+ if inst[0] == 'JUMP_FORWARD':
+ if inst[1] == c:
+ forward_p = 1
+ if not forward_p:
+ continue
+ constraints.append((index[c], i))
+
+ if not constraints:
+ break
+
+ # XXX just do one for now
+ # do swaps to get things in the right order
+ goes_before, a_chain = constraints[0]
+ assert a_chain > goes_before
+ c = chains[a_chain]
+ chains.remove(c)
+ chains.insert(goes_before, c)
+
+
+ del blocks[:]
+ for c in chains:
+ for b in c:
+ blocks.append(b)
+
def getBlocks(self):
return self.blocks.elements()
diff --git a/Lib/compiler/pycodegen.py b/Lib/compiler/pycodegen.py
index 691232f..63b0a57 100644
--- a/Lib/compiler/pycodegen.py
+++ b/Lib/compiler/pycodegen.py
@@ -193,7 +193,7 @@ class CodeGenerator:
else:
self.emit(prefix + '_GLOBAL', name)
- def set_lineno(self, node):
+ def set_lineno(self, node, force=0):
"""Emit SET_LINENO if node has lineno attribute and it is
different than the last lineno emitted.
@@ -205,7 +205,8 @@ class CodeGenerator:
then, this method works around missing line numbers.
"""
lineno = getattr(node, 'lineno', None)
- if lineno is not None and lineno != self.last_lineno:
+ if lineno is not None and (lineno != self.last_lineno
+ or force):
self.emit('SET_LINENO', lineno)
self.last_lineno = lineno
return 1
@@ -413,9 +414,6 @@ class CodeGenerator:
__list_count = 0
def visitListComp(self, node):
- # XXX would it be easier to transform the AST into the form it
- # would have if the list comp were expressed as a series of
- # for and if stmts and an explicit append?
self.set_lineno(node)
# setup list
append = "$append%d" % self.__list_count
@@ -423,10 +421,10 @@ class CodeGenerator:
self.emit('BUILD_LIST', 0)
self.emit('DUP_TOP')
self.emit('LOAD_ATTR', 'append')
- self.storeName(append)
- l = len(node.quals)
+ self.emit('STORE_FAST', append)
+
stack = []
- for i, for_ in zip(range(l), node.quals):
+ for i, for_ in zip(range(len(node.quals)), node.quals):
start, anchor = self.visit(for_)
cont = None
for if_ in for_.ifs:
@@ -434,8 +432,8 @@ class CodeGenerator:
cont = self.newBlock()
self.visit(if_, cont)
stack.insert(0, (start, cont, anchor))
-
- self.loadName(append)
+
+ self.emit('LOAD_FAST', append)
self.visit(node.expr)
self.emit('CALL_FUNCTION', 1)
self.emit('POP_TOP')
@@ -449,12 +447,11 @@ class CodeGenerator:
self.nextBlock(skip_one)
self.emit('JUMP_ABSOLUTE', start)
self.startBlock(anchor)
- self.delName(append)
+ self.emit('DELETE_FAST', append)
self.__list_count = self.__list_count - 1
def visitListCompFor(self, node):
- self.set_lineno(node)
start = self.newBlock()
anchor = self.newBlock()
@@ -468,7 +465,7 @@ class CodeGenerator:
return start, anchor
def visitListCompIf(self, node, branch):
- self.set_lineno(node)
+ self.set_lineno(node, force=1)
self.visit(node.test)
self.emit('JUMP_IF_FALSE', branch)
self.newBlock()
@@ -672,6 +669,7 @@ class CodeGenerator:
print node
def _visitAssSequence(self, node, op='UNPACK_SEQUENCE'):
+## print >> sys.stderr, "AssSequence", op, findOp(node), node
if findOp(node) != 'OP_DELETE':
self.emit(op, len(node.nodes))
for child in node.nodes:
diff --git a/Tools/compiler/compiler/pyassem.py b/Tools/compiler/compiler/pyassem.py
index 15e91f4..e8810ae 100644
--- a/Tools/compiler/compiler/pyassem.py
+++ b/Tools/compiler/compiler/pyassem.py
@@ -27,11 +27,12 @@ class FlowGraph:
if self._debug:
if self.current:
print "end", repr(self.current)
+ print " next", self.current.next
print " ", self.current.get_children()
print repr(block)
self.current = block
- def nextBlock(self, block=None, force=0):
+ def nextBlock(self, block=None):
# XXX think we need to specify when there is implicit transfer
# from one block to the next. might be better to represent this
# with explicit JUMP_ABSOLUTE instructions that are optimized
@@ -95,12 +96,110 @@ class FlowGraph:
b.addNext(self.exit)
order = dfs_postorder(self.entry, {})
order.reverse()
+ self.fixupOrder(order, self.exit)
# hack alert
if not self.exit in order:
order.append(self.exit)
return order
+ def fixupOrder(self, blocks, default_next):
+ """Fixup bad order introduced by DFS."""
+
+ # XXX This is a total mess. There must be a better way to get
+ # the code blocks in the right order.
+
+ self.fixupOrderHonorNext(blocks, default_next)
+ self.fixupOrderForward(blocks, default_next)
+
+ def fixupOrderHonorNext(self, blocks, default_next):
+ """Fix one problem with DFS.
+
+ The DFS uses child block, but doesn't know about the special
+ "next" block. As a result, the DFS can order blocks so that a
+ block isn't next to the right block for implicit control
+ transfers.
+ """
+ index = {}
+ for i in range(len(blocks)):
+ index[blocks[i]] = i
+
+ for i in range(0, len(blocks) - 1):
+ b = blocks[i]
+ n = blocks[i + 1]
+ if not b.next or b.next[0] == default_next or b.next[0] == n:
+ continue
+ # The blocks are in the wrong order. Find the chain of
+ # blocks to insert where they belong.
+ cur = b
+ chain = []
+ elt = cur
+ while elt.next and elt.next[0] != default_next:
+ chain.append(elt.next[0])
+ elt = elt.next[0]
+ # Now remove the blocks in the chain from the current
+ # block list, so that they can be re-inserted.
+ l = []
+ for b in chain:
+ assert index[b] > i
+ l.append((index[b], b))
+ l.sort()
+ l.reverse()
+ for j, b in l:
+ del blocks[index[b]]
+ # Insert the chain in the proper location
+ blocks[i:i + 1] = [cur] + chain
+ # Finally, re-compute the block indexes
+ for i in range(len(blocks)):
+ index[blocks[i]] = i
+
+ def fixupOrderForward(self, blocks, default_next):
+ """Make sure all JUMP_FORWARDs jump forward"""
+ index = {}
+ chains = []
+ cur = []
+ for b in blocks:
+ index[b] = len(chains)
+ cur.append(b)
+ if b.next and b.next[0] == default_next:
+ chains.append(cur)
+ cur = []
+ chains.append(cur)
+
+ while 1:
+ constraints = []
+
+ for i in range(len(chains)):
+ l = chains[i]
+ for b in l:
+ for c in b.get_children():
+ if index[c] < i:
+ forward_p = 0
+ for inst in b.insts:
+ if inst[0] == 'JUMP_FORWARD':
+ if inst[1] == c:
+ forward_p = 1
+ if not forward_p:
+ continue
+ constraints.append((index[c], i))
+
+ if not constraints:
+ break
+
+ # XXX just do one for now
+ # do swaps to get things in the right order
+ goes_before, a_chain = constraints[0]
+ assert a_chain > goes_before
+ c = chains[a_chain]
+ chains.remove(c)
+ chains.insert(goes_before, c)
+
+
+ del blocks[:]
+ for c in chains:
+ for b in c:
+ blocks.append(b)
+
def getBlocks(self):
return self.blocks.elements()
diff --git a/Tools/compiler/compiler/pycodegen.py b/Tools/compiler/compiler/pycodegen.py
index 691232f..63b0a57 100644
--- a/Tools/compiler/compiler/pycodegen.py
+++ b/Tools/compiler/compiler/pycodegen.py
@@ -193,7 +193,7 @@ class CodeGenerator:
else:
self.emit(prefix + '_GLOBAL', name)
- def set_lineno(self, node):
+ def set_lineno(self, node, force=0):
"""Emit SET_LINENO if node has lineno attribute and it is
different than the last lineno emitted.
@@ -205,7 +205,8 @@ class CodeGenerator:
then, this method works around missing line numbers.
"""
lineno = getattr(node, 'lineno', None)
- if lineno is not None and lineno != self.last_lineno:
+ if lineno is not None and (lineno != self.last_lineno
+ or force):
self.emit('SET_LINENO', lineno)
self.last_lineno = lineno
return 1
@@ -413,9 +414,6 @@ class CodeGenerator:
__list_count = 0
def visitListComp(self, node):
- # XXX would it be easier to transform the AST into the form it
- # would have if the list comp were expressed as a series of
- # for and if stmts and an explicit append?
self.set_lineno(node)
# setup list
append = "$append%d" % self.__list_count
@@ -423,10 +421,10 @@ class CodeGenerator:
self.emit('BUILD_LIST', 0)
self.emit('DUP_TOP')
self.emit('LOAD_ATTR', 'append')
- self.storeName(append)
- l = len(node.quals)
+ self.emit('STORE_FAST', append)
+
stack = []
- for i, for_ in zip(range(l), node.quals):
+ for i, for_ in zip(range(len(node.quals)), node.quals):
start, anchor = self.visit(for_)
cont = None
for if_ in for_.ifs:
@@ -434,8 +432,8 @@ class CodeGenerator:
cont = self.newBlock()
self.visit(if_, cont)
stack.insert(0, (start, cont, anchor))
-
- self.loadName(append)
+
+ self.emit('LOAD_FAST', append)
self.visit(node.expr)
self.emit('CALL_FUNCTION', 1)
self.emit('POP_TOP')
@@ -449,12 +447,11 @@ class CodeGenerator:
self.nextBlock(skip_one)
self.emit('JUMP_ABSOLUTE', start)
self.startBlock(anchor)
- self.delName(append)
+ self.emit('DELETE_FAST', append)
self.__list_count = self.__list_count - 1
def visitListCompFor(self, node):
- self.set_lineno(node)
start = self.newBlock()
anchor = self.newBlock()
@@ -468,7 +465,7 @@ class CodeGenerator:
return start, anchor
def visitListCompIf(self, node, branch):
- self.set_lineno(node)
+ self.set_lineno(node, force=1)
self.visit(node.test)
self.emit('JUMP_IF_FALSE', branch)
self.newBlock()
@@ -672,6 +669,7 @@ class CodeGenerator:
print node
def _visitAssSequence(self, node, op='UNPACK_SEQUENCE'):
+## print >> sys.stderr, "AssSequence", op, findOp(node), node
if findOp(node) != 'OP_DELETE':
self.emit(op, len(node.nodes))
for child in node.nodes: