Source

mino-pypy / pypy / interpreter / astcompiler / optimize.py

Full commit
Armin Rigo fe457c4 


Stephen Tu e852266 
Stephen Tu b99efe3 
Stephen Tu e852266 
Armin Rigo fe457c4 


Amaury Forgeot d… 693b081 
Armin Rigo fe457c4 




Stephen Tu e852266 
Stephen Tu fcaf37b 




Armin Rigo fe457c4 















Armin Rigo aba0616 
Armin Rigo fe457c4 


Armin Rigo aba0616 





Armin Rigo fe457c4 

Benjamin Peterso… 81cdb58 
Armin Rigo fe457c4 
Benjamin Peterso… 81cdb58 
Armin Rigo fe457c4 


















Alex Gaynor b644f00 








Armin Rigo fe457c4 

























































Alex Gaynor b644f00 
Armin Rigo fe457c4 










Armin Rigo bb527bd 
Armin Rigo c782efd 
Armin Rigo fe457c4 





































































































































Alex Gaynor b644f00 







Amaury Forgeot d… 693b081 
Alex Gaynor b644f00 
Amaury Forgeot d… 693b081 









Benjamin Peterso… 7e8d570 
Amaury Forgeot d… 693b081 
Armin Rigo 27558fb 












Amaury Forgeot d… 693b081 


Alex Gaynor b644f00 
Stephen Tu e852266 



Stephen Tu b99efe3 
Stephen Tu e852266 















Stephen Tu 6c7bc01 


Stephen Tu 9b0cff4 
Stephen Tu 6c7bc01 
Stephen Tu e852266 

Stephen Tu 500dd27 



























Stephen Tu 9315337 



Stephen Tu 500dd27 



























Stephen Tu e852266 
Stephen Tu 083d5e0 

Stephen Tu 8fb095a 
Stephen Tu fcaf37b 
Stephen Tu 500dd27 































Stephen Tu e852266 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
"""codegen helpers and AST constant folding."""
import sys

from pypy.interpreter.astcompiler import ast, consts, misc, astbuilder
from pypy.interpreter.pyparser import pyparse
from pypy.interpreter.pyparser.pygram import syms
from pypy.tool import stdlib_opcode as ops
from pypy.interpreter.error import OperationError
from pypy.rlib.unroll import unrolling_iterable
from pypy.rlib.runicode import MAXUNICODE


def optimize_ast(space, tree, compile_info):
    return tree.mutate_over(OptimizingVisitor(space, compile_info))

def instrument_ast(space, tree, compile_info):
    b = astbuilder.ASTBuilder(space, None, compile_info)
    if b.do_instrument_file():
        return tree.mutate_over(InstrumentingVisitor(space, compile_info))
    else:
        return tree

CONST_NOT_CONST = -1
CONST_FALSE = 0
CONST_TRUE = 1


class __extend__(ast.AST):

    def as_constant_truth(self, space):
        """Return the truth of this node if known."""
        const = self.as_constant()
        if const is None:
            return CONST_NOT_CONST
        return int(space.is_true(const))

    def as_constant(self):
        """Return the value of this node as a wrapped constant if possible."""
        return None

    def accept_jump_if(self, gen, condition, target):
        raise AssertionError("only for expressions")


class __extend__(ast.expr):

    def accept_jump_if(self, gen, condition, target):
        self.walkabout(gen)
        if condition:
            gen.emit_jump(ops.POP_JUMP_IF_TRUE, target, True)
        else:
            gen.emit_jump(ops.POP_JUMP_IF_FALSE, target, True)


class __extend__(ast.Num):

    def as_constant(self):
        return self.n


class __extend__(ast.Str):

    def as_constant(self):
        return self.s


class __extend__(ast.Const):

    def as_constant(self):
        return self.value

class __extend__(ast.Index):
    def as_constant(self):
        return self.value.as_constant()

class __extend__(ast.Slice):
    def as_constant(self):
        # XXX: this ought to return a slice object if all the indices are
        # constants, but we don't have a space here.
        return None

class __extend__(ast.UnaryOp):

    def accept_jump_if(self, gen, condition, target):
        if self.op == ast.Not:
            self.operand.accept_jump_if(gen, not condition, target)
        else:
            ast.expr.accept_jump_if(self, gen, condition, target)



class __extend__(ast.BoolOp):

    def _accept_jump_if_any_is(self, gen, condition, target):
        self.values[0].accept_jump_if(gen, condition, target)
        for i in range(1, len(self.values)):
            self.values[i].accept_jump_if(gen, condition, target)

    def accept_jump_if(self, gen, condition, target):
        if condition and self.op == ast.And or \
                (not condition and self.op == ast.Or):
            end = gen.new_block()
            self._accept_jump_if_any_is(gen, not condition, end)
            gen.emit_jump(ops.JUMP_FORWARD, target)
            gen.use_next_block(end)
        else:
            self._accept_jump_if_any_is(gen, condition, target)


def _binary_fold(name):
    def do_fold(space, left, right):
        return getattr(space, name)(left, right)
    return do_fold

def _unary_fold(name):
    def do_fold(space, operand):
        return getattr(space, name)(operand)
    return do_fold

def _fold_pow(space, left, right):
    return space.pow(left, right, space.w_None)

def _fold_not(space, operand):
    return space.wrap(not space.is_true(operand))


binary_folders = {
    ast.Add : _binary_fold("add"),
    ast.Sub : _binary_fold("sub"),
    ast.Mult : _binary_fold("mul"),
    ast.Div : _binary_fold("truediv"),
    ast.FloorDiv : _binary_fold("floordiv"),
    ast.Mod : _binary_fold("mod"),
    ast.Pow : _fold_pow,
    ast.LShift : _binary_fold("lshift"),
    ast.RShift : _binary_fold("rshift"),
    ast.BitOr : _binary_fold("or_"),
    ast.BitXor : _binary_fold("xor"),
    ast.BitAnd : _binary_fold("and_"),
}
unrolling_binary_folders = unrolling_iterable(binary_folders.items())

unary_folders = {
    ast.Not : _fold_not,
    ast.USub : _unary_fold("neg"),
    ast.UAdd : _unary_fold("pos"),
    ast.Invert : _unary_fold("invert")
}
unrolling_unary_folders = unrolling_iterable(unary_folders.items())

for folder in binary_folders.values() + unary_folders.values():
    folder._always_inline_ = 'try'
del folder

opposite_compare_operations = misc.dict_to_switch({
    ast.Is : ast.IsNot,
    ast.IsNot : ast.Is,
    ast.In : ast.NotIn,
    ast.NotIn : ast.In
})


class OptimizingVisitor(ast.ASTVisitor):
    """Constant folds AST."""

    def __init__(self, space, compile_info):
        self.space = space
        self.compile_info = compile_info

    def default_visitor(self, node):
        return node

    def visit_BinOp(self, binop):
        left = binop.left.as_constant()
        if left is not None:
            right = binop.right.as_constant()
            if right is not None:
                op = binop.op
                # Can't fold straight division without "from __future_ import
                # division" because it might be affected at runtime by the -Q
                # flag.
                if op == ast.Div and \
                        not self.compile_info.flags & consts.CO_FUTURE_DIVISION:
                    return binop
                try:
                    for op_kind, folder in unrolling_binary_folders:
                        if op_kind == op:
                            w_const = folder(self.space, left, right)
                            break
                    else:
                        raise AssertionError("unknown binary operation")
                # Let all errors be found at runtime.
                except OperationError:
                    pass
                else:
                    # To avoid blowing up the size of pyc files, we only fold
                    # reasonably sized sequences.
                    try:
                        w_len = self.space.len(w_const)
                    except OperationError:
                        pass
                    else:
                        if self.space.int_w(w_len) > 20:
                            return binop
                    return ast.Const(w_const, binop.lineno, binop.col_offset)
        return binop

    def visit_UnaryOp(self, unary):
        w_operand = unary.operand.as_constant()
        op = unary.op
        if w_operand is not None:
            try:
                for op_kind, folder in unrolling_unary_folders:
                    if op_kind == op:
                        w_const = folder(self.space, w_operand)
                        break
                else:
                    raise AssertionError("unknown unary operation")
                w_minint = self.space.wrap(-sys.maxint - 1)
                # This makes sure the result is an integer.
                if self.space.eq_w(w_minint, w_const):
                    w_const = w_minint
            except OperationError:
                pass
            else:
                return ast.Const(w_const, unary.lineno, unary.col_offset)
        elif op == ast.Not:
            compare = unary.operand
            if isinstance(compare, ast.Compare) and len(compare.ops) == 1:
                cmp_op = compare.ops[0]
                try:
                    opposite = opposite_compare_operations(cmp_op)
                except KeyError:
                    pass
                else:
                    compare.ops[0] = opposite
                    return compare
        return unary

    def visit_BoolOp(self, bop):
        values = bop.values
        we_are_and = bop.op == ast.And
        i = 0
        while i < len(values) - 1:
            truth = values[i].as_constant_truth(self.space)
            if truth != CONST_NOT_CONST:
                if (truth != CONST_TRUE) == we_are_and:
                    del values[i + 1:]
                    break
                else:
                    del values[i]
            else:
                i += 1
        if len(values) == 1:
            return values[0]
        return bop

    def visit_Repr(self, rep):
        w_const = rep.value.as_constant()
        if w_const is not None:
            w_repr = self.space.repr(w_const)
            return ast.Const(w_repr, rep.lineno, rep.col_offset)
        return rep

    def visit_Name(self, name):
        # Turn loading None into a constant lookup.  Eventaully, we can do this
        # for True and False, too.
        if name.id == "None":
            assert name.ctx == ast.Load
            return ast.Const(self.space.w_None, name.lineno, name.col_offset)
        return name

    def visit_Tuple(self, tup):
        """Try to turn tuple building into a constant."""
        if tup.elts:
            consts_w = [None]*len(tup.elts)
            for i in range(len(tup.elts)):
                node = tup.elts[i]
                w_const = node.as_constant()
                if w_const is None:
                    return tup
                consts_w[i] = w_const
        else:
            consts_w = []
        w_consts = self.space.newtuple(consts_w)
        return ast.Const(w_consts, tup.lineno, tup.col_offset)

    def visit_Subscript(self, subs):
        if subs.ctx == ast.Load:
            w_obj = subs.value.as_constant()
            if w_obj is not None:
                w_idx = subs.slice.as_constant()
                if w_idx is not None:
                    try:
                        w_const = self.space.getitem(w_obj, w_idx)
                    except OperationError:
                        # Let exceptions propagate at runtime.
                        return subs

                    # CPython issue5057: if v is unicode, there might
                    # be differences between wide and narrow builds in
                    # cases like u'\U00012345'[0].
                    # Wide builds will return a non-BMP char, whereas
                    # narrow builds will return a surrogate.  In both
                    # the cases skip the optimization in order to
                    # produce compatible pycs.
                    if (self.space.isinstance_w(w_obj, self.space.w_unicode) and
                        self.space.isinstance_w(w_const, self.space.w_unicode)):
                        #unistr = self.space.unicode_w(w_const)
                        #if len(unistr) == 1:
                        #    ch = ord(unistr[0])
                        #else:
                        #    ch = 0
                        #if (ch > 0xFFFF or
                        #    (MAXUNICODE == 0xFFFF and 0xD800 <= ch <= 0xDFFF)):
                        # --XXX-- for now we always disable optimization of
                        # u'...'[constant] because the tests above are not
                        # enough to fix issue5057 (CPython has the same
                        # problem as of April 24, 2012).
                        # See test_const_fold_unicode_subscr
                        return subs

                    return ast.Const(w_const, subs.lineno, subs.col_offset)

        return subs

class InstrumentingVisitor(ast.ASTVisitor):

    ### XXX: hacky
    _HIDDEN_NAME_ = astbuilder.ASTBuilder._HIDDEN_NAME_

    def __init__(self, space, compile_info):
        self.space = space
        self.compile_info = compile_info

        ### XXX: hacky- we only want this for it's dummy_parser and
        ### for handle_stmt()
        self.ast_builder = astbuilder.ASTBuilder(space, None, compile_info)

    def default_visitor(self, node):
        return node

    def _mutate_sequence(self, seq):
        for i in range(len(seq)):
            # check to see if the next elem is the function element
            # representing the instrumentation- if so, DO NOT RECURSE!
            node = seq[i]
            if isinstance(node, ast.FunctionDef):
                if node.name == self._HIDDEN_NAME_:
                    #print "found instrumentor, skipping..."
                    continue
            seq[i] = seq[i].mutate_over(self)

    def _unravel_instr_sequence(self, unravel):
        '''
        checks to see if unravel represents a sequence of
        dotted names like a.b.c

        returns a string representing the unraveled path a.b.c
        '''

        # base case- names are good
        if isinstance(unravel, ast.Name):
            return unravel.id

        # otherwise, if we see a call to our instrumentation, unwrap it
        elif isinstance(unravel, ast.Call):
            if isinstance(unravel.func, ast.Name) and \
               unravel.func.id == astbuilder.ASTBuilder._HIDDEN_NAME_:
                 return self._unravel_instr_sequence(unravel.args[4])

        # the attr case
        elif isinstance(unravel, ast.Attribute):
            uvalue = self._unravel_instr_sequence(unravel.value)
            if uvalue:
                return uvalue + "." + unravel.attr

        # out of luck
        return None

    def _break_if_file_matches(self, filename):
        pass
        #if self.compile_info.filename.find(filename) != -1:
        #    import pdb
        #    pdb.set_trace()

    def visit_Attribute(self, attr):
        #self._break_if_file_matches('yy.py')

        if attr.ctx != ast.Load:
            return ast.ASTVisitor.visit_Attribute(self, attr)

        dname = self._unravel_instr_sequence(attr)
        if not dname:
            return ast.ASTVisitor.visit_Attribute(self, attr)

        # wrap this AST node in a call, with dname
        lno = attr.lineno
        cno = attr.col_offset
        return ast.Call(
            ast.Name(self._HIDDEN_NAME_, ast.Load, lno, cno), # func
            [ast.Str(self.space.wrap(self.compile_info.filename), lno, cno),
             ast.Num(self.space.wrap(lno), lno, cno),
             ast.Num(self.space.wrap(cno), lno, cno),
             ast.Str(self.space.wrap(dname), lno, cno),
             attr], # args
            None, # keywords
            None, # starargs
            None, # kwargs
            lno, # lineno
            cno # col_offset
          )

    def visit_Name(self, name):
        #import pdb
        #pdb.set_trace()
        if name.ctx == ast.Load \
           and name.id not in ['None', 'True', 'False']:

            #my_source = '''%s('%s', %d, %d, '%s', %s)''' % (
            #    self._HIDDEN_NAME_, self.compile_info.filename,
            #    name.lineno, name.col_offset, name.id, name.id)
            #ci = pyparse.CompileInfo(self.compile_info.filename,
            #                         self.compile_info.mode,
            #                         self.compile_info.flags)
            #my_pt = self.ast_builder.dummy_parser.parse_source(my_source, ci)
            #assert my_pt.type == syms.file_input
            #assert my_pt.children[0].type == syms.stmt
            #my_ast = self.ast_builder.handle_stmt(my_pt.children[0]).value
            ##assert type(my_ast) == ast.Call
            #v = astbuilder.LineNumberVisitor(name.lineno, name.col_offset)
            #my_ast.mutate_over(v)
            #assert my_ast.lineno == name.lineno
            #return my_ast

            lno = name.lineno
            cno = name.col_offset
            return ast.Call(
                ast.Name(self._HIDDEN_NAME_, ast.Load, lno, cno), # func
                [ast.Str(self.space.wrap(self.compile_info.filename), lno, cno),
                 ast.Num(self.space.wrap(lno), lno, cno),
                 ast.Num(self.space.wrap(cno), lno, cno),
                 ast.Str(self.space.wrap(name.id), lno, cno),
                 name], # args
                None, # keywords
                None, # starargs
                None, # kwargs
                lno, # lineno
                cno # col_offset
              )
        else:
            # don't bother w/ stores, delets, etc
            return name