1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/compiler/pyassem.py Fri May 18 23:26:30 2012 +0200
1.3 @@ -0,0 +1,763 @@
1.4 +"""A flow graph representation for Python bytecode"""
1.5 +
1.6 +import dis
1.7 +import types
1.8 +import sys
1.9 +
1.10 +from compiler import misc
1.11 +from compiler.consts \
1.12 + import CO_OPTIMIZED, CO_NEWLOCALS, CO_VARARGS, CO_VARKEYWORDS
1.13 +
1.14 +class FlowGraph:
1.15 + def __init__(self):
1.16 + self.current = self.entry = Block()
1.17 + self.exit = Block("exit")
1.18 + self.blocks = misc.Set()
1.19 + self.blocks.add(self.entry)
1.20 + self.blocks.add(self.exit)
1.21 +
1.22 + def startBlock(self, block):
1.23 + if self._debug:
1.24 + if self.current:
1.25 + print "end", repr(self.current)
1.26 + print " next", self.current.next
1.27 + print " prev", self.current.prev
1.28 + print " ", self.current.get_children()
1.29 + print repr(block)
1.30 + self.current = block
1.31 +
1.32 + def nextBlock(self, block=None):
1.33 + # XXX think we need to specify when there is implicit transfer
1.34 + # from one block to the next. might be better to represent this
1.35 + # with explicit JUMP_ABSOLUTE instructions that are optimized
1.36 + # out when they are unnecessary.
1.37 + #
1.38 + # I think this strategy works: each block has a child
1.39 + # designated as "next" which is returned as the last of the
1.40 + # children. because the nodes in a graph are emitted in
1.41 + # reverse post order, the "next" block will always be emitted
1.42 + # immediately after its parent.
1.43 + # Worry: maintaining this invariant could be tricky
1.44 + if block is None:
1.45 + block = self.newBlock()
1.46 +
1.47 + # Note: If the current block ends with an unconditional control
1.48 + # transfer, then it is techically incorrect to add an implicit
1.49 + # transfer to the block graph. Doing so results in code generation
1.50 + # for unreachable blocks. That doesn't appear to be very common
1.51 + # with Python code and since the built-in compiler doesn't optimize
1.52 + # it out we don't either.
1.53 + self.current.addNext(block)
1.54 + self.startBlock(block)
1.55 +
1.56 + def newBlock(self):
1.57 + b = Block()
1.58 + self.blocks.add(b)
1.59 + return b
1.60 +
1.61 + def startExitBlock(self):
1.62 + self.startBlock(self.exit)
1.63 +
1.64 + _debug = 0
1.65 +
1.66 + def _enable_debug(self):
1.67 + self._debug = 1
1.68 +
1.69 + def _disable_debug(self):
1.70 + self._debug = 0
1.71 +
1.72 + def emit(self, *inst):
1.73 + if self._debug:
1.74 + print "\t", inst
1.75 + if len(inst) == 2 and isinstance(inst[1], Block):
1.76 + self.current.addOutEdge(inst[1])
1.77 + self.current.emit(inst)
1.78 +
1.79 + def getBlocksInOrder(self):
1.80 + """Return the blocks in reverse postorder
1.81 +
1.82 + i.e. each node appears before all of its successors
1.83 + """
1.84 + order = order_blocks(self.entry, self.exit)
1.85 + return order
1.86 +
1.87 + def getBlocks(self):
1.88 + return self.blocks.elements()
1.89 +
1.90 + def getRoot(self):
1.91 + """Return nodes appropriate for use with dominator"""
1.92 + return self.entry
1.93 +
1.94 + def getContainedGraphs(self):
1.95 + l = []
1.96 + for b in self.getBlocks():
1.97 + l.extend(b.getContainedGraphs())
1.98 + return l
1.99 +
1.100 +
1.101 +def order_blocks(start_block, exit_block):
1.102 + """Order blocks so that they are emitted in the right order"""
1.103 + # Rules:
1.104 + # - when a block has a next block, the next block must be emitted just after
1.105 + # - when a block has followers (relative jumps), it must be emitted before
1.106 + # them
1.107 + # - all reachable blocks must be emitted
1.108 + order = []
1.109 +
1.110 + # Find all the blocks to be emitted.
1.111 + remaining = set()
1.112 + todo = [start_block]
1.113 + while todo:
1.114 + b = todo.pop()
1.115 + if b in remaining:
1.116 + continue
1.117 + remaining.add(b)
1.118 + for c in b.get_children():
1.119 + if c not in remaining:
1.120 + todo.append(c)
1.121 +
1.122 + # A block is dominated by another block if that block must be emitted
1.123 + # before it.
1.124 + dominators = {}
1.125 + for b in remaining:
1.126 + if __debug__ and b.next:
1.127 + assert b is b.next[0].prev[0], (b, b.next)
1.128 + # Make sure every block appears in dominators, even if no
1.129 + # other block must precede it.
1.130 + dominators.setdefault(b, set())
1.131 + # preceeding blocks dominate following blocks
1.132 + for c in b.get_followers():
1.133 + while 1:
1.134 + dominators.setdefault(c, set()).add(b)
1.135 + # Any block that has a next pointer leading to c is also
1.136 + # dominated because the whole chain will be emitted at once.
1.137 + # Walk backwards and add them all.
1.138 + if c.prev and c.prev[0] is not b:
1.139 + c = c.prev[0]
1.140 + else:
1.141 + break
1.142 +
1.143 + def find_next():
1.144 + # Find a block that can be emitted next.
1.145 + for b in remaining:
1.146 + for c in dominators[b]:
1.147 + if c in remaining:
1.148 + break # can't emit yet, dominated by a remaining block
1.149 + else:
1.150 + return b
1.151 + assert 0, 'circular dependency, cannot find next block'
1.152 +
1.153 + b = start_block
1.154 + while 1:
1.155 + order.append(b)
1.156 + remaining.discard(b)
1.157 + if b.next:
1.158 + b = b.next[0]
1.159 + continue
1.160 + elif b is not exit_block and not b.has_unconditional_transfer():
1.161 + order.append(exit_block)
1.162 + if not remaining:
1.163 + break
1.164 + b = find_next()
1.165 + return order
1.166 +
1.167 +
1.168 +class Block:
1.169 + _count = 0
1.170 +
1.171 + def __init__(self, label=''):
1.172 + self.insts = []
1.173 + self.outEdges = set()
1.174 + self.label = label
1.175 + self.bid = Block._count
1.176 + self.next = []
1.177 + self.prev = []
1.178 + Block._count = Block._count + 1
1.179 +
1.180 + def __repr__(self):
1.181 + if self.label:
1.182 + return "<block %s id=%d>" % (self.label, self.bid)
1.183 + else:
1.184 + return "<block id=%d>" % (self.bid)
1.185 +
1.186 + def __str__(self):
1.187 + insts = map(str, self.insts)
1.188 + return "<block %s %d:\n%s>" % (self.label, self.bid,
1.189 + '\n'.join(insts))
1.190 +
1.191 + def emit(self, inst):
1.192 + op = inst[0]
1.193 + self.insts.append(inst)
1.194 +
1.195 + def getInstructions(self):
1.196 + return self.insts
1.197 +
1.198 + def addOutEdge(self, block):
1.199 + self.outEdges.add(block)
1.200 +
1.201 + def addNext(self, block):
1.202 + self.next.append(block)
1.203 + assert len(self.next) == 1, map(str, self.next)
1.204 + block.prev.append(self)
1.205 + assert len(block.prev) == 1, map(str, block.prev)
1.206 +
1.207 + _uncond_transfer = ('RETURN_VALUE', 'RAISE_VARARGS',
1.208 + 'JUMP_ABSOLUTE', 'JUMP_FORWARD', 'CONTINUE_LOOP',
1.209 + )
1.210 +
1.211 + def has_unconditional_transfer(self):
1.212 + """Returns True if there is an unconditional transfer to an other block
1.213 + at the end of this block. This means there is no risk for the bytecode
1.214 + executer to go past this block's bytecode."""
1.215 + try:
1.216 + op, arg = self.insts[-1]
1.217 + except (IndexError, ValueError):
1.218 + return
1.219 + return op in self._uncond_transfer
1.220 +
1.221 + def get_children(self):
1.222 + return list(self.outEdges) + self.next
1.223 +
1.224 + def get_followers(self):
1.225 + """Get the whole list of followers, including the next block."""
1.226 + followers = set(self.next)
1.227 + # Blocks that must be emitted *after* this one, because of
1.228 + # bytecode offsets (e.g. relative jumps) pointing to them.
1.229 + for inst in self.insts:
1.230 + if inst[0] in PyFlowGraph.hasjrel:
1.231 + followers.add(inst[1])
1.232 + return followers
1.233 +
1.234 + def getContainedGraphs(self):
1.235 + """Return all graphs contained within this block.
1.236 +
1.237 + For example, a MAKE_FUNCTION block will contain a reference to
1.238 + the graph for the function body.
1.239 + """
1.240 + contained = []
1.241 + for inst in self.insts:
1.242 + if len(inst) == 1:
1.243 + continue
1.244 + op = inst[1]
1.245 + if hasattr(op, 'graph'):
1.246 + contained.append(op.graph)
1.247 + return contained
1.248 +
1.249 +# flags for code objects
1.250 +
1.251 +# the FlowGraph is transformed in place; it exists in one of these states
1.252 +RAW = "RAW"
1.253 +FLAT = "FLAT"
1.254 +CONV = "CONV"
1.255 +DONE = "DONE"
1.256 +
1.257 +class PyFlowGraph(FlowGraph):
1.258 + super_init = FlowGraph.__init__
1.259 +
1.260 + def __init__(self, name, filename, args=(), optimized=0, klass=None):
1.261 + self.super_init()
1.262 + self.name = name
1.263 + self.filename = filename
1.264 + self.docstring = None
1.265 + self.args = args # XXX
1.266 + self.argcount = getArgCount(args)
1.267 + self.klass = klass
1.268 + if optimized:
1.269 + self.flags = CO_OPTIMIZED | CO_NEWLOCALS
1.270 + else:
1.271 + self.flags = 0
1.272 + self.consts = []
1.273 + self.names = []
1.274 + # Free variables found by the symbol table scan, including
1.275 + # variables used only in nested scopes, are included here.
1.276 + self.freevars = []
1.277 + self.cellvars = []
1.278 + # The closure list is used to track the order of cell
1.279 + # variables and free variables in the resulting code object.
1.280 + # The offsets used by LOAD_CLOSURE/LOAD_DEREF refer to both
1.281 + # kinds of variables.
1.282 + self.closure = []
1.283 + self.varnames = list(args) or []
1.284 + for i in range(len(self.varnames)):
1.285 + var = self.varnames[i]
1.286 + if isinstance(var, TupleArg):
1.287 + self.varnames[i] = var.getName()
1.288 + self.stage = RAW
1.289 +
1.290 + def setDocstring(self, doc):
1.291 + self.docstring = doc
1.292 +
1.293 + def setFlag(self, flag):
1.294 + self.flags = self.flags | flag
1.295 + if flag == CO_VARARGS:
1.296 + self.argcount = self.argcount - 1
1.297 +
1.298 + def checkFlag(self, flag):
1.299 + if self.flags & flag:
1.300 + return 1
1.301 +
1.302 + def setFreeVars(self, names):
1.303 + self.freevars = list(names)
1.304 +
1.305 + def setCellVars(self, names):
1.306 + self.cellvars = names
1.307 +
1.308 + def getCode(self):
1.309 + """Get a Python code object"""
1.310 + assert self.stage == RAW
1.311 + self.computeStackDepth()
1.312 + self.flattenGraph()
1.313 + assert self.stage == FLAT
1.314 + self.convertArgs()
1.315 + assert self.stage == CONV
1.316 + self.makeByteCode()
1.317 + assert self.stage == DONE
1.318 + return self.newCodeObject()
1.319 +
1.320 + def dump(self, io=None):
1.321 + if io:
1.322 + save = sys.stdout
1.323 + sys.stdout = io
1.324 + pc = 0
1.325 + for t in self.insts:
1.326 + opname = t[0]
1.327 + if opname == "SET_LINENO":
1.328 + print
1.329 + if len(t) == 1:
1.330 + print "\t", "%3d" % pc, opname
1.331 + pc = pc + 1
1.332 + else:
1.333 + print "\t", "%3d" % pc, opname, t[1]
1.334 + pc = pc + 3
1.335 + if io:
1.336 + sys.stdout = save
1.337 +
1.338 + def computeStackDepth(self):
1.339 + """Compute the max stack depth.
1.340 +
1.341 + Approach is to compute the stack effect of each basic block.
1.342 + Then find the path through the code with the largest total
1.343 + effect.
1.344 + """
1.345 + depth = {}
1.346 + exit = None
1.347 + for b in self.getBlocks():
1.348 + depth[b] = findDepth(b.getInstructions())
1.349 +
1.350 + seen = {}
1.351 +
1.352 + def max_depth(b, d):
1.353 + if b in seen:
1.354 + return d
1.355 + seen[b] = 1
1.356 + d = d + depth[b]
1.357 + children = b.get_children()
1.358 + if children:
1.359 + return max([max_depth(c, d) for c in children])
1.360 + else:
1.361 + if not b.label == "exit":
1.362 + return max_depth(self.exit, d)
1.363 + else:
1.364 + return d
1.365 +
1.366 + self.stacksize = max_depth(self.entry, 0)
1.367 +
1.368 + def flattenGraph(self):
1.369 + """Arrange the blocks in order and resolve jumps"""
1.370 + assert self.stage == RAW
1.371 + self.insts = insts = []
1.372 + pc = 0
1.373 + begin = {}
1.374 + end = {}
1.375 + for b in self.getBlocksInOrder():
1.376 + begin[b] = pc
1.377 + for inst in b.getInstructions():
1.378 + insts.append(inst)
1.379 + if len(inst) == 1:
1.380 + pc = pc + 1
1.381 + elif inst[0] != "SET_LINENO":
1.382 + # arg takes 2 bytes
1.383 + pc = pc + 3
1.384 + end[b] = pc
1.385 + pc = 0
1.386 + for i in range(len(insts)):
1.387 + inst = insts[i]
1.388 + if len(inst) == 1:
1.389 + pc = pc + 1
1.390 + elif inst[0] != "SET_LINENO":
1.391 + pc = pc + 3
1.392 + opname = inst[0]
1.393 + if opname in self.hasjrel:
1.394 + oparg = inst[1]
1.395 + offset = begin[oparg] - pc
1.396 + insts[i] = opname, offset
1.397 + elif opname in self.hasjabs:
1.398 + insts[i] = opname, begin[inst[1]]
1.399 + self.stage = FLAT
1.400 +
1.401 + hasjrel = set()
1.402 + for i in dis.hasjrel:
1.403 + hasjrel.add(dis.opname[i])
1.404 + hasjabs = set()
1.405 + for i in dis.hasjabs:
1.406 + hasjabs.add(dis.opname[i])
1.407 +
1.408 + def convertArgs(self):
1.409 + """Convert arguments from symbolic to concrete form"""
1.410 + assert self.stage == FLAT
1.411 + self.consts.insert(0, self.docstring)
1.412 + self.sort_cellvars()
1.413 + for i in range(len(self.insts)):
1.414 + t = self.insts[i]
1.415 + if len(t) == 2:
1.416 + opname, oparg = t
1.417 + conv = self._converters.get(opname, None)
1.418 + if conv:
1.419 + self.insts[i] = opname, conv(self, oparg)
1.420 + self.stage = CONV
1.421 +
1.422 + def sort_cellvars(self):
1.423 + """Sort cellvars in the order of varnames and prune from freevars.
1.424 + """
1.425 + cells = {}
1.426 + for name in self.cellvars:
1.427 + cells[name] = 1
1.428 + self.cellvars = [name for name in self.varnames
1.429 + if name in cells]
1.430 + for name in self.cellvars:
1.431 + del cells[name]
1.432 + self.cellvars = self.cellvars + cells.keys()
1.433 + self.closure = self.cellvars + self.freevars
1.434 +
1.435 + def _lookupName(self, name, list):
1.436 + """Return index of name in list, appending if necessary
1.437 +
1.438 + This routine uses a list instead of a dictionary, because a
1.439 + dictionary can't store two different keys if the keys have the
1.440 + same value but different types, e.g. 2 and 2L. The compiler
1.441 + must treat these two separately, so it does an explicit type
1.442 + comparison before comparing the values.
1.443 + """
1.444 + t = type(name)
1.445 + for i in range(len(list)):
1.446 + if t == type(list[i]) and list[i] == name:
1.447 + return i
1.448 + end = len(list)
1.449 + list.append(name)
1.450 + return end
1.451 +
1.452 + _converters = {}
1.453 + def _convert_LOAD_CONST(self, arg):
1.454 + if hasattr(arg, 'getCode'):
1.455 + arg = arg.getCode()
1.456 + return self._lookupName(arg, self.consts)
1.457 +
1.458 + def _convert_LOAD_FAST(self, arg):
1.459 + self._lookupName(arg, self.names)
1.460 + return self._lookupName(arg, self.varnames)
1.461 + _convert_STORE_FAST = _convert_LOAD_FAST
1.462 + _convert_DELETE_FAST = _convert_LOAD_FAST
1.463 +
1.464 + def _convert_LOAD_NAME(self, arg):
1.465 + if self.klass is None:
1.466 + self._lookupName(arg, self.varnames)
1.467 + return self._lookupName(arg, self.names)
1.468 +
1.469 + def _convert_NAME(self, arg):
1.470 + if self.klass is None:
1.471 + self._lookupName(arg, self.varnames)
1.472 + return self._lookupName(arg, self.names)
1.473 + _convert_STORE_NAME = _convert_NAME
1.474 + _convert_DELETE_NAME = _convert_NAME
1.475 + _convert_IMPORT_NAME = _convert_NAME
1.476 + _convert_IMPORT_FROM = _convert_NAME
1.477 + _convert_STORE_ATTR = _convert_NAME
1.478 + _convert_LOAD_ATTR = _convert_NAME
1.479 + _convert_DELETE_ATTR = _convert_NAME
1.480 + _convert_LOAD_GLOBAL = _convert_NAME
1.481 + _convert_STORE_GLOBAL = _convert_NAME
1.482 + _convert_DELETE_GLOBAL = _convert_NAME
1.483 +
1.484 + def _convert_DEREF(self, arg):
1.485 + self._lookupName(arg, self.names)
1.486 + self._lookupName(arg, self.varnames)
1.487 + return self._lookupName(arg, self.closure)
1.488 + _convert_LOAD_DEREF = _convert_DEREF
1.489 + _convert_STORE_DEREF = _convert_DEREF
1.490 +
1.491 + def _convert_LOAD_CLOSURE(self, arg):
1.492 + self._lookupName(arg, self.varnames)
1.493 + return self._lookupName(arg, self.closure)
1.494 +
1.495 + _cmp = list(dis.cmp_op)
1.496 + def _convert_COMPARE_OP(self, arg):
1.497 + return self._cmp.index(arg)
1.498 +
1.499 + # similarly for other opcodes...
1.500 +
1.501 + for name, obj in locals().items():
1.502 + if name[:9] == "_convert_":
1.503 + opname = name[9:]
1.504 + _converters[opname] = obj
1.505 + del name, obj, opname
1.506 +
1.507 + def makeByteCode(self):
1.508 + assert self.stage == CONV
1.509 + self.lnotab = lnotab = LineAddrTable()
1.510 + for t in self.insts:
1.511 + opname = t[0]
1.512 + if len(t) == 1:
1.513 + lnotab.addCode(self.opnum[opname])
1.514 + else:
1.515 + oparg = t[1]
1.516 + if opname == "SET_LINENO":
1.517 + lnotab.nextLine(oparg)
1.518 + continue
1.519 + hi, lo = twobyte(oparg)
1.520 + try:
1.521 + lnotab.addCode(self.opnum[opname], lo, hi)
1.522 + except ValueError:
1.523 + print opname, oparg
1.524 + print self.opnum[opname], lo, hi
1.525 + raise
1.526 + self.stage = DONE
1.527 +
1.528 + opnum = {}
1.529 + for num in range(len(dis.opname)):
1.530 + opnum[dis.opname[num]] = num
1.531 + del num
1.532 +
1.533 + def newCodeObject(self):
1.534 + assert self.stage == DONE
1.535 + if (self.flags & CO_NEWLOCALS) == 0:
1.536 + nlocals = 0
1.537 + else:
1.538 + nlocals = len(self.varnames)
1.539 + argcount = self.argcount
1.540 + if self.flags & CO_VARKEYWORDS:
1.541 + argcount = argcount - 1
1.542 + return types.CodeType(argcount, nlocals, self.stacksize, self.flags,
1.543 + self.lnotab.getCode(), self.getConsts(),
1.544 + tuple(self.names), tuple(self.varnames),
1.545 + self.filename, self.name, self.lnotab.firstline,
1.546 + self.lnotab.getTable(), tuple(self.freevars),
1.547 + tuple(self.cellvars))
1.548 +
1.549 + def getConsts(self):
1.550 + """Return a tuple for the const slot of the code object
1.551 +
1.552 + Must convert references to code (MAKE_FUNCTION) to code
1.553 + objects recursively.
1.554 + """
1.555 + l = []
1.556 + for elt in self.consts:
1.557 + if isinstance(elt, PyFlowGraph):
1.558 + elt = elt.getCode()
1.559 + l.append(elt)
1.560 + return tuple(l)
1.561 +
1.562 +def isJump(opname):
1.563 + if opname[:4] == 'JUMP':
1.564 + return 1
1.565 +
1.566 +class TupleArg:
1.567 + """Helper for marking func defs with nested tuples in arglist"""
1.568 + def __init__(self, count, names):
1.569 + self.count = count
1.570 + self.names = names
1.571 + def __repr__(self):
1.572 + return "TupleArg(%s, %s)" % (self.count, self.names)
1.573 + def getName(self):
1.574 + return ".%d" % self.count
1.575 +
1.576 +def getArgCount(args):
1.577 + argcount = len(args)
1.578 + if args:
1.579 + for arg in args:
1.580 + if isinstance(arg, TupleArg):
1.581 + numNames = len(misc.flatten(arg.names))
1.582 + argcount = argcount - numNames
1.583 + return argcount
1.584 +
1.585 +def twobyte(val):
1.586 + """Convert an int argument into high and low bytes"""
1.587 + assert isinstance(val, int)
1.588 + return divmod(val, 256)
1.589 +
1.590 +class LineAddrTable:
1.591 + """lnotab
1.592 +
1.593 + This class builds the lnotab, which is documented in compile.c.
1.594 + Here's a brief recap:
1.595 +
1.596 + For each SET_LINENO instruction after the first one, two bytes are
1.597 + added to lnotab. (In some cases, multiple two-byte entries are
1.598 + added.) The first byte is the distance in bytes between the
1.599 + instruction for the last SET_LINENO and the current SET_LINENO.
1.600 + The second byte is offset in line numbers. If either offset is
1.601 + greater than 255, multiple two-byte entries are added -- see
1.602 + compile.c for the delicate details.
1.603 + """
1.604 +
1.605 + def __init__(self):
1.606 + self.code = []
1.607 + self.codeOffset = 0
1.608 + self.firstline = 0
1.609 + self.lastline = 0
1.610 + self.lastoff = 0
1.611 + self.lnotab = []
1.612 +
1.613 + def addCode(self, *args):
1.614 + for arg in args:
1.615 + self.code.append(chr(arg))
1.616 + self.codeOffset = self.codeOffset + len(args)
1.617 +
1.618 + def nextLine(self, lineno):
1.619 + if self.firstline == 0:
1.620 + self.firstline = lineno
1.621 + self.lastline = lineno
1.622 + else:
1.623 + # compute deltas
1.624 + addr = self.codeOffset - self.lastoff
1.625 + line = lineno - self.lastline
1.626 + # Python assumes that lineno always increases with
1.627 + # increasing bytecode address (lnotab is unsigned char).
1.628 + # Depending on when SET_LINENO instructions are emitted
1.629 + # this is not always true. Consider the code:
1.630 + # a = (1,
1.631 + # b)
1.632 + # In the bytecode stream, the assignment to "a" occurs
1.633 + # after the loading of "b". This works with the C Python
1.634 + # compiler because it only generates a SET_LINENO instruction
1.635 + # for the assignment.
1.636 + if line >= 0:
1.637 + push = self.lnotab.append
1.638 + while addr > 255:
1.639 + push(255); push(0)
1.640 + addr -= 255
1.641 + while line > 255:
1.642 + push(addr); push(255)
1.643 + line -= 255
1.644 + addr = 0
1.645 + if addr > 0 or line > 0:
1.646 + push(addr); push(line)
1.647 + self.lastline = lineno
1.648 + self.lastoff = self.codeOffset
1.649 +
1.650 + def getCode(self):
1.651 + return ''.join(self.code)
1.652 +
1.653 + def getTable(self):
1.654 + return ''.join(map(chr, self.lnotab))
1.655 +
1.656 +class StackDepthTracker:
1.657 + # XXX 1. need to keep track of stack depth on jumps
1.658 + # XXX 2. at least partly as a result, this code is broken
1.659 +
1.660 + def findDepth(self, insts, debug=0):
1.661 + depth = 0
1.662 + maxDepth = 0
1.663 + for i in insts:
1.664 + opname = i[0]
1.665 + if debug:
1.666 + print i,
1.667 + delta = self.effect.get(opname, None)
1.668 + if delta is not None:
1.669 + depth = depth + delta
1.670 + else:
1.671 + # now check patterns
1.672 + for pat, pat_delta in self.patterns:
1.673 + if opname[:len(pat)] == pat:
1.674 + delta = pat_delta
1.675 + depth = depth + delta
1.676 + break
1.677 + # if we still haven't found a match
1.678 + if delta is None:
1.679 + meth = getattr(self, opname, None)
1.680 + if meth is not None:
1.681 + depth = depth + meth(i[1])
1.682 + if depth > maxDepth:
1.683 + maxDepth = depth
1.684 + if debug:
1.685 + print depth, maxDepth
1.686 + return maxDepth
1.687 +
1.688 + effect = {
1.689 + 'POP_TOP': -1,
1.690 + 'DUP_TOP': 1,
1.691 + 'LIST_APPEND': -1,
1.692 + 'SET_ADD': -1,
1.693 + 'MAP_ADD': -2,
1.694 + 'SLICE+1': -1,
1.695 + 'SLICE+2': -1,
1.696 + 'SLICE+3': -2,
1.697 + 'STORE_SLICE+0': -1,
1.698 + 'STORE_SLICE+1': -2,
1.699 + 'STORE_SLICE+2': -2,
1.700 + 'STORE_SLICE+3': -3,
1.701 + 'DELETE_SLICE+0': -1,
1.702 + 'DELETE_SLICE+1': -2,
1.703 + 'DELETE_SLICE+2': -2,
1.704 + 'DELETE_SLICE+3': -3,
1.705 + 'STORE_SUBSCR': -3,
1.706 + 'DELETE_SUBSCR': -2,
1.707 + # PRINT_EXPR?
1.708 + 'PRINT_ITEM': -1,
1.709 + 'RETURN_VALUE': -1,
1.710 + 'YIELD_VALUE': -1,
1.711 + 'EXEC_STMT': -3,
1.712 + 'BUILD_CLASS': -2,
1.713 + 'STORE_NAME': -1,
1.714 + 'STORE_ATTR': -2,
1.715 + 'DELETE_ATTR': -1,
1.716 + 'STORE_GLOBAL': -1,
1.717 + 'BUILD_MAP': 1,
1.718 + 'COMPARE_OP': -1,
1.719 + 'STORE_FAST': -1,
1.720 + 'IMPORT_STAR': -1,
1.721 + 'IMPORT_NAME': -1,
1.722 + 'IMPORT_FROM': 1,
1.723 + 'LOAD_ATTR': 0, # unlike other loads
1.724 + # close enough...
1.725 + 'SETUP_EXCEPT': 3,
1.726 + 'SETUP_FINALLY': 3,
1.727 + 'FOR_ITER': 1,
1.728 + 'WITH_CLEANUP': -1,
1.729 + }
1.730 + # use pattern match
1.731 + patterns = [
1.732 + ('BINARY_', -1),
1.733 + ('LOAD_', 1),
1.734 + ]
1.735 +
1.736 + def UNPACK_SEQUENCE(self, count):
1.737 + return count-1
1.738 + def BUILD_TUPLE(self, count):
1.739 + return -count+1
1.740 + def BUILD_LIST(self, count):
1.741 + return -count+1
1.742 + def BUILD_SET(self, count):
1.743 + return -count+1
1.744 + def CALL_FUNCTION(self, argc):
1.745 + hi, lo = divmod(argc, 256)
1.746 + return -(lo + hi * 2)
1.747 + def CALL_FUNCTION_VAR(self, argc):
1.748 + return self.CALL_FUNCTION(argc)-1
1.749 + def CALL_FUNCTION_KW(self, argc):
1.750 + return self.CALL_FUNCTION(argc)-1
1.751 + def CALL_FUNCTION_VAR_KW(self, argc):
1.752 + return self.CALL_FUNCTION(argc)-2
1.753 + def MAKE_FUNCTION(self, argc):
1.754 + return -argc
1.755 + def MAKE_CLOSURE(self, argc):
1.756 + # XXX need to account for free variables too!
1.757 + return -argc
1.758 + def BUILD_SLICE(self, argc):
1.759 + if argc == 2:
1.760 + return -1
1.761 + elif argc == 3:
1.762 + return -2
1.763 + def DUP_TOPX(self, argc):
1.764 + return argc
1.765 +
1.766 +findDepth = StackDepthTracker().findDepth