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