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