Lib/compiler/pyassem.py

   1 """A flow graph representation for Python bytecode"""
   2
   3 import dis
   4 import new
   5 import string
   6 import sys
   7 import types
   8
   9 from compiler import misc
  10 from compiler.consts import CO_OPTIMIZED, CO_NEWLOCALS, CO_VARARGS, \
  11      CO_VARKEYWORDS
  12
  13 def xxx_sort(l):
  14     l = l[:]
  15     def sorter(a, b):
  16         return cmp(a.bid, b.bid)
  17     l.sort(sorter)
  18     return l
  19
  20 class FlowGraph:
  21     def __init__(self):
  22         self.current = self.entry = Block()
  23         self.exit = Block("exit")
  24         self.blocks = misc.Set()
  25         self.blocks.add(self.entry)
  26         self.blocks.add(self.exit)
  27
  28     def startBlock(self, block):
  29         if self._debug:
  30             if self.current:
  31                 print "end", repr(self.current)
  32                 print "    next", self.current.next
  33                 print "   ", self.current.get_children()
  34             print repr(block)
  35         self.current = block
  36
  37     def nextBlock(self, block=None):
  38         # XXX think we need to specify when there is implicit transfer
  39         # from one block to the next.  might be better to represent this
  40         # with explicit JUMP_ABSOLUTE instructions that are optimized
  41         # out when they are unnecessary.
  42         #
  43         # I think this strategy works: each block has a child
  44         # designated as "next" which is returned as the last of the
  45         # children.  because the nodes in a graph are emitted in
  46         # reverse post order, the "next" block will always be emitted
  47         # immediately after its parent.
  48         # Worry: maintaining this invariant could be tricky
  49         if block is None:
  50             block = self.newBlock()
  51
  52         # Note: If the current block ends with an unconditional
  53         # control transfer, then it is incorrect to add an implicit
  54         # transfer to the block graph.  The current code requires
  55         # these edges to get the blocks emitted in the right order,
  56         # however. :-(  If a client needs to remove these edges, call
  57         # pruneEdges().
  58
  59         self.current.addNext(block)
  60         self.startBlock(block)
  61
  62     def newBlock(self):
  63         b = Block()
  64         self.blocks.add(b)
  65         return b
  66
  67     def startExitBlock(self):
  68         self.startBlock(self.exit)
  69
  70     _debug = 0
  71
  72     def _enable_debug(self):
  73         self._debug = 1
  74
  75     def _disable_debug(self):
  76         self._debug = 0
  77
  78     def emit(self, *inst):
  79         if self._debug:
  80             print "\t", inst
  81         if inst[0] == 'RETURN_VALUE':
  82             self.current.addOutEdge(self.exit)
  83         if len(inst) == 2 and isinstance(inst[1], Block):
  84             self.current.addOutEdge(inst[1])
  85         self.current.emit(inst)
  86
  87     def getBlocksInOrder(self):
  88         """Return the blocks in reverse postorder
  89
  90         i.e. each node appears before all of its successors
  91         """
  92         # XXX make sure every node that doesn't have an explicit next
  93         # is set so that next points to exit
  94         for b in self.blocks.elements():
  95             if b is self.exit:
  96                 continue
  97             if not b.next:
  98                 b.addNext(self.exit)
  99         order = dfs_postorder(self.entry, {})
 100         order.reverse()
 101         self.fixupOrder(order, self.exit)
 102         # hack alert
 103         if not self.exit in order:
 104             order.append(self.exit)
 105
 106         return order
 107
 108     def fixupOrder(self, blocks, default_next):
 109         """Fixup bad order introduced by DFS."""
 110
 111         # XXX This is a total mess.  There must be a better way to get
 112         # the code blocks in the right order.
 113
 114         self.fixupOrderHonorNext(blocks, default_next)
 115         self.fixupOrderForward(blocks, default_next)
 116
 117     def fixupOrderHonorNext(self, blocks, default_next):
 118         """Fix one problem with DFS.
 119
 120         The DFS uses child block, but doesn't know about the special
 121         "next" block.  As a result, the DFS can order blocks so that a
 122         block isn't next to the right block for implicit control
 123         transfers.
 124         """
 125         index = {}
 126         for i in range(len(blocks)):
 127             index[blocks[i]] = i
 128
 129         for i in range(0, len(blocks) - 1):
 130             b = blocks[i]
 131             n = blocks[i + 1]
 132             if not b.next or b.next[0] == default_next or b.next[0] == n:
 133                 continue
 134             # The blocks are in the wrong order.  Find the chain of
 135             # blocks to insert where they belong.
 136             cur = b
 137             chain = []
 138             elt = cur
 139             while elt.next and elt.next[0] != default_next:
 140                 chain.append(elt.next[0])
 141                 elt = elt.next[0]
 142             # Now remove the blocks in the chain from the current
 143             # block list, so that they can be re-inserted.
 144             l = []
 145             for b in chain:
 146                 assert index[b] > i
 147                 l.append((index[b], b))
 148             l.sort()
 149             l.reverse()
 150             for j, b in l:
 151                 del blocks[index[b]]
 152             # Insert the chain in the proper location
 153             blocks[i:i + 1] = [cur] + chain
 154             # Finally, re-compute the block indexes
 155             for i in range(len(blocks)):
 156                 index[blocks[i]] = i
 157
 158     def fixupOrderForward(self, blocks, default_next):
 159         """Make sure all JUMP_FORWARDs jump forward"""
 160         index = {}
 161         chains = []
 162         cur = []
 163         for b in blocks:
 164             index[b] = len(chains)
 165             cur.append(b)
 166             if b.next and b.next[0] == default_next:
 167                 chains.append(cur)
 168                 cur = []
 169         chains.append(cur)
 170
 171         while 1:
 172             constraints = []
 173
 174             for i in range(len(chains)):
 175                 l = chains[i]
 176                 for b in l:
 177                     for c in b.get_children():
 178                         if index[c] < i:
 179                             forward_p = 0
 180                             for inst in b.insts:
 181                                 if inst[0] == 'JUMP_FORWARD':
 182                                     if inst[1] == c:
 183                                         forward_p = 1
 184                             if not forward_p:
 185                                 continue
 186                             constraints.append((index[c], i))
 187
 188             if not constraints:
 189                 break
 190
 191             # XXX just do one for now
 192             # do swaps to get things in the right order
 193             goes_before, a_chain = constraints[0]
 194             assert a_chain > goes_before
 195             c = chains[a_chain]
 196             chains.remove(c)
 197             chains.insert(goes_before, c)
 198
 199         del blocks[:]
 200         for c in chains:
 201             for b in c:
 202                 blocks.append(b)
 203
 204     def getBlocks(self):
 205         return self.blocks.elements()
 206
 207     def getRoot(self):
 208         """Return nodes appropriate for use with dominator"""
 209         return self.entry
 210
 211     def getContainedGraphs(self):
 212         l = []
 213         for b in self.getBlocks():
 214             l.extend(b.getContainedGraphs())
 215         return l
 216
 217 def dfs_postorder(b, seen):
 218     """Depth-first search of tree rooted at b, return in postorder"""
 219     order = []
 220     seen[b] = b
 221     for c in b.get_children():
 222         if seen.has_key(c):
 223             continue
 224         order = order + dfs_postorder(c, seen)
 225     order.append(b)
 226     return order
 227
 228 class Block:
 229     _count = 0
 230
 231     def __init__(self, label=''):
 232         self.insts = []
 233         self.inEdges = misc.Set()
 234         self.outEdges = misc.Set()
 235         self.label = label
 236         self.bid = Block._count
 237         self.next = []
 238         Block._count = Block._count + 1
 239
 240     def __repr__(self):
 241         if self.label:
 242             return "<block %s id=%d>" % (self.label, self.bid)
 243         else:
 244             return "<block id=%d>" % (self.bid)
 245
 246     def __str__(self):
 247         insts = map(str, self.insts)
 248         return "<block %s %d:\n%s>" % (self.label, self.bid,
 249                                        string.join(insts, '\n'))
 250
 251     def emit(self, inst):
 252         op = inst[0]
 253         if op[:4] == 'JUMP':
 254             self.outEdges.add(inst[1])
 255         self.insts.append(inst)
 256
 257     def getInstructions(self):
 258         return self.insts
 259
 260     def addInEdge(self, block):
 261         self.inEdges.add(block)
 262
 263     def addOutEdge(self, block):
 264         self.outEdges.add(block)
 265
 266     def addNext(self, block):
 267         self.next.append(block)
 268         assert len(self.next) == 1, map(str, self.next)
 269
 270     _uncond_transfer = ('RETURN_VALUE', 'RAISE_VARARGS',
 271                         'JUMP_ABSOLUTE', 'JUMP_FORWARD', 'CONTINUE_LOOP')
 272
 273     def pruneNext(self):
 274         """Remove bogus edge for unconditional transfers
 275
 276         Each block has a next edge that accounts for implicit control
 277         transfers, e.g. from a JUMP_IF_FALSE to the block that will be
 278         executed if the test is true.
 279
 280         These edges must remain for the current assembler code to
 281         work. If they are removed, the dfs_postorder gets things in
 282         weird orders.  However, they shouldn't be there for other
 283         purposes, e.g. conversion to SSA form.  This method will
 284         remove the next edge when it follows an unconditional control
 285         transfer.
 286         """
 287         try:
 288             op, arg = self.insts[-1]
 289         except (IndexError, ValueError):
 290             return
 291         if op in self._uncond_transfer:
 292             self.next = []
 293
 294     def get_children(self):
 295         if self.next and self.next[0] in self.outEdges:
 296             self.outEdges.remove(self.next[0])
 297         return self.outEdges.elements() + self.next
 298
 299     def getContainedGraphs(self):
 300         """Return all graphs contained within this block.
 301
 302         For example, a MAKE_FUNCTION block will contain a reference to
 303         the graph for the function body.
 304         """
 305         contained = []
 306         for inst in self.insts:
 307             if len(inst) == 1:
 308                 continue
 309             op = inst[1]
 310             if hasattr(op, 'graph'):
 311                 contained.append(op.graph)
 312         return contained
 313
 314 # flags for code objects
 315
 316 # the FlowGraph is transformed in place; it exists in one of these states
 317 RAW = "RAW"
 318 FLAT = "FLAT"
 319 CONV = "CONV"
 320 DONE = "DONE"
 321
 322 class PyFlowGraph(FlowGraph):
 323     super_init = FlowGraph.__init__
 324
 325     def __init__(self, name, filename, args=(), optimized=0, klass=None):
 326         self.super_init()
 327         self.name = name
 328         self.filename = filename
 329         self.docstring = None
 330         self.args = args # XXX
 331         self.argcount = getArgCount(args)
 332         self.klass = klass
 333         if optimized:
 334             self.flags = CO_OPTIMIZED | CO_NEWLOCALS
 335         else:
 336             self.flags = 0
 337         self.consts = []
 338         self.names = []
 339         # Free variables found by the symbol table scan, including
 340         # variables used only in nested scopes, are included here.
 341         self.freevars = []
 342         self.cellvars = []
 343         # The closure list is used to track the order of cell
 344         # variables and free variables in the resulting code object.
 345         # The offsets used by LOAD_CLOSURE/LOAD_DEREF refer to both
 346         # kinds of variables.
 347         self.closure = []
 348         self.varnames = list(args) or []
 349         for i in range(len(self.varnames)):
 350             var = self.varnames[i]
 351             if isinstance(var, TupleArg):
 352                 self.varnames[i] = var.getName()
 353         self.stage = RAW
 354
 355     def setDocstring(self, doc):
 356         self.docstring = doc
 357
 358     def setFlag(self, flag):
 359         self.flags = self.flags | flag
 360         if flag == CO_VARARGS:
 361             self.argcount = self.argcount - 1
 362
 363     def checkFlag(self, flag):
 364         if self.flags & flag:
 365             return 1
 366
 367     def setFreeVars(self, names):
 368         self.freevars = list(names)
 369
 370     def setCellVars(self, names):
 371         self.cellvars = names
 372
 373     def getCode(self):
 374         """Get a Python code object"""
 375         if self.stage == RAW:
 376             self.computeStackDepth()
 377             self.flattenGraph()
 378         if self.stage == FLAT:
 379             self.convertArgs()
 380         if self.stage == CONV:
 381             self.makeByteCode()
 382         if self.stage == DONE:
 383             return self.newCodeObject()
 384         raise RuntimeError, "inconsistent PyFlowGraph state"
 385
 386     def dump(self, io=None):
 387         if io:
 388             save = sys.stdout
 389             sys.stdout = io
 390         pc = 0
 391         for t in self.insts:
 392             opname = t[0]
 393             if opname == "SET_LINENO":
 394                 print
 395             if len(t) == 1:
 396                 print "\t", "%3d" % pc, opname
 397                 pc = pc + 1
 398             else:
 399                 print "\t", "%3d" % pc, opname, t[1]
 400                 pc = pc + 3
 401         if io:
 402             sys.stdout = save
 403
 404     def computeStackDepth(self):
 405         """Compute the max stack depth.
 406
 407         Approach is to compute the stack effect of each basic block.
 408         Then find the path through the code with the largest total
 409         effect.
 410         """
 411         depth = {}
 412         exit = None
 413         for b in self.getBlocks():
 414             depth[b] = findDepth(b.getInstructions())
 415
 416         seen = {}
 417
 418         def max_depth(b, d):
 419             if seen.has_key(b):
 420                 return d
 421             seen[b] = 1
 422             d = d + depth[b]
 423             children = b.get_children()
 424             if children:
 425                 return max([max_depth(c, d) for c in children])
 426             else:
 427                 if not b.label == "exit":
 428                     return max_depth(self.exit, d)
 429                 else:
 430                     return d
 431
 432         self.stacksize = max_depth(self.entry, 0)
 433
 434     def flattenGraph(self):
 435         """Arrange the blocks in order and resolve jumps"""
 436         assert self.stage == RAW
 437         self.insts = insts = []
 438         pc = 0
 439         begin = {}
 440         end = {}
 441         for b in self.getBlocksInOrder():
 442             begin[b] = pc
 443             for inst in b.getInstructions():
 444                 insts.append(inst)
 445                 if len(inst) == 1:
 446                     pc = pc + 1
 447                 else:
 448                     # arg takes 2 bytes
 449                     pc = pc + 3
 450             end[b] = pc
 451         pc = 0
 452         for i in range(len(insts)):
 453             inst = insts[i]
 454             if len(inst) == 1:
 455                 pc = pc + 1
 456             else:
 457                 pc = pc + 3
 458             opname = inst[0]
 459             if self.hasjrel.has_elt(opname):
 460                 oparg = inst[1]
 461                 offset = begin[oparg] - pc
 462                 insts[i] = opname, offset
 463             elif self.hasjabs.has_elt(opname):
 464                 insts[i] = opname, begin[inst[1]]
 465         self.stage = FLAT
 466
 467     hasjrel = misc.Set()
 468     for i in dis.hasjrel:
 469         hasjrel.add(dis.opname[i])
 470     hasjabs = misc.Set()
 471     for i in dis.hasjabs:
 472         hasjabs.add(dis.opname[i])
 473
 474     def convertArgs(self):
 475         """Convert arguments from symbolic to concrete form"""
 476         assert self.stage == FLAT
 477         self.consts.insert(0, self.docstring)
 478         self.sort_cellvars()
 479         for i in range(len(self.insts)):
 480             t = self.insts[i]
 481             if len(t) == 2:
 482                 opname, oparg = t
 483                 conv = self._converters.get(opname, None)
 484                 if conv:
 485                     self.insts[i] = opname, conv(self, oparg)
 486         self.stage = CONV
 487
 488     def sort_cellvars(self):
 489         """Sort cellvars in the order of varnames and prune from freevars.
 490         """
 491         cells = {}
 492         for name in self.cellvars:
 493             cells[name] = 1
 494         self.cellvars = [name for name in self.varnames
 495                          if cells.has_key(name)]
 496         for name in self.cellvars:
 497             del cells[name]
 498         self.cellvars = self.cellvars + cells.keys()
 499         self.closure = self.cellvars + self.freevars
 500
 501     def _lookupName(self, name, list):
 502         """Return index of name in list, appending if necessary
 503
 504         This routine uses a list instead of a dictionary, because a
 505         dictionary can't store two different keys if the keys have the
 506         same value but different types, e.g. 2 and 2L.  The compiler
 507         must treat these two separately, so it does an explicit type
 508         comparison before comparing the values.
 509         """
 510         t = type(name)
 511         for i in range(len(list)):
 512             if t == type(list[i]) and list[i] == name:
 513                 return i
 514         end = len(list)
 515         list.append(name)
 516         return end
 517
 518     _converters = {}
 519     def _convert_LOAD_CONST(self, arg):
 520         if hasattr(arg, 'getCode'):
 521             arg = arg.getCode()
 522         return self._lookupName(arg, self.consts)
 523
 524     def _convert_LOAD_FAST(self, arg):
 525         self._lookupName(arg, self.names)
 526         return self._lookupName(arg, self.varnames)
 527     _convert_STORE_FAST = _convert_LOAD_FAST
 528     _convert_DELETE_FAST = _convert_LOAD_FAST
 529
 530     def _convert_LOAD_NAME(self, arg):
 531         if self.klass is None:
 532             self._lookupName(arg, self.varnames)
 533         return self._lookupName(arg, self.names)
 534
 535     def _convert_NAME(self, arg):
 536         if self.klass is None:
 537             self._lookupName(arg, self.varnames)
 538         return self._lookupName(arg, self.names)
 539     _convert_STORE_NAME = _convert_NAME
 540     _convert_DELETE_NAME = _convert_NAME
 541     _convert_IMPORT_NAME = _convert_NAME
 542     _convert_IMPORT_FROM = _convert_NAME
 543     _convert_STORE_ATTR = _convert_NAME
 544     _convert_LOAD_ATTR = _convert_NAME
 545     _convert_DELETE_ATTR = _convert_NAME
 546     _convert_LOAD_GLOBAL = _convert_NAME
 547     _convert_STORE_GLOBAL = _convert_NAME
 548     _convert_DELETE_GLOBAL = _convert_NAME
 549
 550     def _convert_DEREF(self, arg):
 551         self._lookupName(arg, self.names)
 552         self._lookupName(arg, self.varnames)
 553         return self._lookupName(arg, self.closure)
 554     _convert_LOAD_DEREF = _convert_DEREF
 555     _convert_STORE_DEREF = _convert_DEREF
 556
 557     def _convert_LOAD_CLOSURE(self, arg):
 558         self._lookupName(arg, self.varnames)
 559         return self._lookupName(arg, self.closure)
 560
 561     _cmp = list(dis.cmp_op)
 562     def _convert_COMPARE_OP(self, arg):
 563         return self._cmp.index(arg)
 564
 565     # similarly for other opcodes...
 566
 567     for name, obj in locals().items():
 568         if name[:9] == "_convert_":
 569             opname = name[9:]
 570             _converters[opname] = obj
 571     del name, obj, opname
 572
 573     def makeByteCode(self):
 574         assert self.stage == CONV
 575         self.lnotab = lnotab = LineAddrTable()
 576         for t in self.insts:
 577             opname = t[0]
 578             if len(t) == 1:
 579                 lnotab.addCode(self.opnum[opname])
 580             else:
 581                 oparg = t[1]
 582                 if opname == "SET_LINENO":
 583                     lnotab.nextLine(oparg)
 584                 hi, lo = twobyte(oparg)
 585                 try:
 586                     lnotab.addCode(self.opnum[opname], lo, hi)
 587                 except ValueError:
 588                     print opname, oparg
 589                     print self.opnum[opname], lo, hi
 590                     raise
 591         self.stage = DONE
 592
 593     opnum = {}
 594     for num in range(len(dis.opname)):
 595         opnum[dis.opname[num]] = num
 596     del num
 597
 598     def newCodeObject(self):
 599         assert self.stage == DONE
 600         if (self.flags & CO_NEWLOCALS) == 0:
 601             nlocals = 0
 602         else:
 603             nlocals = len(self.varnames)
 604         argcount = self.argcount
 605         if self.flags & CO_VARKEYWORDS:
 606             argcount = argcount - 1
 607         return new.code(argcount, nlocals, self.stacksize, self.flags,
 608                         self.lnotab.getCode(), self.getConsts(),
 609                         tuple(self.names), tuple(self.varnames),
 610                         self.filename, self.name, self.lnotab.firstline,
 611                         self.lnotab.getTable(), tuple(self.freevars),
 612                         tuple(self.cellvars))
 613
 614     def getConsts(self):
 615         """Return a tuple for the const slot of the code object
 616
 617         Must convert references to code (MAKE_FUNCTION) to code
 618         objects recursively.
 619         """
 620         l = []
 621         for elt in self.consts:
 622             if isinstance(elt, PyFlowGraph):
 623                 elt = elt.getCode()
 624             l.append(elt)
 625         return tuple(l)
 626
 627 def isJump(opname):
 628     if opname[:4] == 'JUMP':
 629         return 1
 630
 631 class TupleArg:
 632     """Helper for marking func defs with nested tuples in arglist"""
 633     def __init__(self, count, names):
 634         self.count = count
 635         self.names = names
 636     def __repr__(self):
 637         return "TupleArg(%s, %s)" % (self.count, self.names)
 638     def getName(self):
 639         return ".%d" % self.count
 640
 641 def getArgCount(args):
 642     argcount = len(args)
 643     if args:
 644         for arg in args:
 645             if isinstance(arg, TupleArg):
 646                 numNames = len(misc.flatten(arg.names))
 647                 argcount = argcount - numNames
 648     return argcount
 649
 650 def twobyte(val):
 651     """Convert an int argument into high and low bytes"""
 652     assert type(val) == types.IntType
 653     return divmod(val, 256)
 654
 655 class LineAddrTable:
 656     """lnotab
 657
 658     This class builds the lnotab, which is documented in compile.c.
 659     Here's a brief recap:
 660
 661     For each SET_LINENO instruction after the first one, two bytes are
 662     added to lnotab.  (In some cases, multiple two-byte entries are
 663     added.)  The first byte is the distance in bytes between the
 664     instruction for the last SET_LINENO and the current SET_LINENO.
 665     The second byte is offset in line numbers.  If either offset is
 666     greater than 255, multiple two-byte entries are added -- see
 667     compile.c for the delicate details.
 668     """
 669
 670     def __init__(self):
 671         self.code = []
 672         self.codeOffset = 0
 673         self.firstline = 0
 674         self.lastline = 0
 675         self.lastoff = 0
 676         self.lnotab = []
 677
 678     def addCode(self, *args):
 679         for arg in args:
 680             self.code.append(chr(arg))
 681         self.codeOffset = self.codeOffset + len(args)
 682
 683     def nextLine(self, lineno):
 684         if self.firstline == 0:
 685             self.firstline = lineno
 686             self.lastline = lineno
 687         else:
 688             # compute deltas
 689             addr = self.codeOffset - self.lastoff
 690             line = lineno - self.lastline
 691             # Python assumes that lineno always increases with
 692             # increasing bytecode address (lnotab is unsigned char).
 693             # Depending on when SET_LINENO instructions are emitted
 694             # this is not always true.  Consider the code:
 695             #     a = (1,
 696             #          b)
 697             # In the bytecode stream, the assignment to "a" occurs
 698             # after the loading of "b".  This works with the C Python
 699             # compiler because it only generates a SET_LINENO instruction
 700             # for the assignment.
 701             if line > 0:
 702                 push = self.lnotab.append
 703                 while addr > 255:
 704                     push(255); push(0)
 705                     addr -= 255
 706                 while line > 255:
 707                     push(addr); push(255)
 708                     line -= 255
 709                     addr = 0
 710                 if addr > 0 or line > 0:
 711                     push(addr); push(line)
 712                 self.lastline = lineno
 713                 self.lastoff = self.codeOffset
 714
 715     def getCode(self):
 716         return string.join(self.code, '')
 717
 718     def getTable(self):
 719         return string.join(map(chr, self.lnotab), '')
 720
 721 class StackDepthTracker:
 722     # XXX 1. need to keep track of stack depth on jumps
 723     # XXX 2. at least partly as a result, this code is broken
 724
 725     def findDepth(self, insts, debug=0):
 726         depth = 0
 727         maxDepth = 0
 728         for i in insts:
 729             opname = i[0]
 730             if debug:
 731                 print i,
 732             delta = self.effect.get(opname, None)
 733             if delta is not None:
 734                 depth = depth + delta
 735             else:
 736                 # now check patterns
 737                 for pat, pat_delta in self.patterns:
 738                     if opname[:len(pat)] == pat:
 739                         delta = pat_delta
 740                         depth = depth + delta
 741                         break
 742                 # if we still haven't found a match
 743                 if delta is None:
 744                     meth = getattr(self, opname, None)
 745                     if meth is not None:
 746                         depth = depth + meth(i[1])
 747             if depth > maxDepth:
 748                 maxDepth = depth
 749             if debug:
 750                 print depth, maxDepth
 751         return maxDepth
 752
 753     effect = {
 754         'POP_TOP': -1,
 755         'DUP_TOP': 1,
 756         'SLICE+1': -1,
 757         'SLICE+2': -1,
 758         'SLICE+3': -2,
 759         'STORE_SLICE+0': -1,
 760         'STORE_SLICE+1': -2,
 761         'STORE_SLICE+2': -2,
 762         'STORE_SLICE+3': -3,
 763         'DELETE_SLICE+0': -1,
 764         'DELETE_SLICE+1': -2,
 765         'DELETE_SLICE+2': -2,
 766         'DELETE_SLICE+3': -3,
 767         'STORE_SUBSCR': -3,
 768         'DELETE_SUBSCR': -2,
 769         # PRINT_EXPR?
 770         'PRINT_ITEM': -1,
 771         'RETURN_VALUE': -1,
 772         'EXEC_STMT': -3,
 773         'BUILD_CLASS': -2,
 774         'STORE_NAME': -1,
 775         'STORE_ATTR': -2,
 776         'DELETE_ATTR': -1,
 777         'STORE_GLOBAL': -1,
 778         'BUILD_MAP': 1,
 779         'COMPARE_OP': -1,
 780         'STORE_FAST': -1,
 781         'IMPORT_STAR': -1,
 782         'IMPORT_NAME': 0,
 783         'IMPORT_FROM': 1,
 784         'LOAD_ATTR': 0, # unlike other loads
 785         # close enough...
 786         'SETUP_EXCEPT': 3,
 787         'SETUP_FINALLY': 3,
 788         'FOR_ITER': 1,
 789         }
 790     # use pattern match
 791     patterns = [
 792         ('BINARY_', -1),
 793         ('LOAD_', 1),
 794         ]
 795
 796     def UNPACK_SEQUENCE(self, count):
 797         return count-1
 798     def BUILD_TUPLE(self, count):
 799         return -count+1
 800     def BUILD_LIST(self, count):
 801         return -count+1
 802     def CALL_FUNCTION(self, argc):
 803         hi, lo = divmod(argc, 256)
 804         return -(lo + hi * 2)
 805     def CALL_FUNCTION_VAR(self, argc):
 806         return self.CALL_FUNCTION(argc)-1
 807     def CALL_FUNCTION_KW(self, argc):
 808         return self.CALL_FUNCTION(argc)-1
 809     def CALL_FUNCTION_VAR_KW(self, argc):
 810         return self.CALL_FUNCTION(argc)-2
 811     def MAKE_FUNCTION(self, argc):
 812         return -argc
 813     def MAKE_CLOSURE(self, argc):
 814         # XXX need to account for free variables too!
 815         return -argc
 816     def BUILD_SLICE(self, argc):
 817         if argc == 2:
 818             return -1
 819         elif argc == 3:
 820             return -2
 821     def DUP_TOPX(self, argc):
 822         return argc
 823
 824 findDepth = StackDepthTracker().findDepth