# HG changeset patch # User Paul Boddie # Date 1226175311 -3600 # Node ID a40a277b13323696078aade96a0898e19dcc0fbf # Parent 390c6b60cc04c3819e882e39a0e86c06bbef5b79 Moved optimisations onto instances of the Importer class, using such instances from InspectedModule and Translation instances. Removed the optimisations parameter from the get_image methods and the initialisers of the affected classes. Moved various built-in values to a predefined constants list in the InspectedModule class. Changed lambda object inspection to return an Instance where a dynamic object would be required; this requires a corresponding alteration in the Translation class to prevent optimisations being attempted on the Instance, although such optimisations could be permitted in future. Refined the all_objects attribute on InspectedModule instances to only contain Class and Function instances. Added support for checking whether objects have been referenced, introducing instance attributes on data objects for this purpose. Firstly, during inspection, use of the names of classes and functions is tracked. Subsequently, unreferenced classes and functions (but not methods) are removed from the all_objects list. Finally, during translation, the code of unreferenced classes and functions is suppressed. Added an "unused objects" optimisation using the reference checking support. Changed module reference storage to always involve attribute objects, not bare module objects. diff -r 390c6b60cc04 -r a40a277b1332 lib/builtins.py --- a/lib/builtins.py Tue Oct 28 01:08:06 2008 +0100 +++ b/lib/builtins.py Sat Nov 08 21:15:11 2008 +0100 @@ -262,17 +262,10 @@ # Various types. -class EllipsisType: pass +class ellipsis: pass class NoneType: pass class NotImplementedType: pass -# Special values. - -True = bool() -False = bool() -Ellipsis = EllipsisType() -NotImplemented = NotImplementedType() - # General functions. # NOTE: Some of these are actually provided by classes in CPython. # NOTE: We may refuse to support some of these in practice, such as... @@ -331,4 +324,17 @@ def vars(obj=None): pass def zip(*args): pass +# Reference some names to ensure their existence. This should be everything +# mentioned in a get_builtin or load_builtin call. Instances from this module +# should be predefined constants. + +function +list +tuple +xrange +AttributeError +StopIteration +TypeError +ellipsis + # vim: tabstop=4 expandtab shiftwidth=4 diff -r 390c6b60cc04 -r a40a277b1332 micropython/__init__.py --- a/micropython/__init__.py Tue Oct 28 01:08:06 2008 +0100 +++ b/micropython/__init__.py Sat Nov 08 21:15:11 2008 +0100 @@ -53,17 +53,21 @@ supported_optimisations = micropython.opt.Optimiser.supported_optimisations - def __init__(self, path=None, verbose=0): + def __init__(self, path=None, optimisations=None, verbose=0): """ Initialise the importer with the given search 'path' - a list of directories to search for Python modules. + The optional 'optimisations' cause certain techniques to be used in + reducing program size and improving program efficiency. + The optional 'verbose' parameter causes output concerning the activities of the object to be produced if set to a true value (not the default). """ self.path = path or [os.getcwd()] + self.optimisations = optimisations self.verbose = verbose self.modules = {} self.modules_ordered = [] @@ -124,7 +128,7 @@ return self.modules.values() - def get_image(self, with_builtins=0, optimisations=None): + def get_image(self, with_builtins=0): "Return a dictionary mapping modules to structures." @@ -155,7 +159,7 @@ # Position the module in the image and make a translation. module.location = pos - trans = micropython.ast.Translation(module, self, optimisations) + trans = micropython.ast.Translation(module, self) # Add header details. diff -r 390c6b60cc04 -r a40a277b1332 micropython/ast.py --- a/micropython/ast.py Tue Oct 28 01:08:06 2008 +0100 +++ b/micropython/ast.py Sat Nov 08 21:15:11 2008 +0100 @@ -42,11 +42,11 @@ name_load_instructions = (LoadName, LoadAddress) name_store_instructions = (StoreName, StoreAddress) - def __init__(self, module, importer, optimisations=None): + def __init__(self, module, importer): """ - Initialise the translation with an inspected 'module', the 'importer' - and optional 'optimisations'. + Initialise the translation with an inspected 'module' and the module + 'importer'. """ ASTVisitor.__init__(self) @@ -62,7 +62,7 @@ # Optimisation. - self.optimiser = Optimiser(self, optimisations) + self.optimiser = Optimiser(self, importer.optimisations) # The current unit being translated. @@ -211,6 +211,9 @@ else: return "builtins" + def get_predefined_constant(self, name): + return self.module.constant_values[self.module.predefined_constants[name]] + def load_builtin(self, name, node): "Generate an instruction loading 'name' for the given 'node'." @@ -624,6 +627,8 @@ t = self.optimiser.optimise_known_target() if t: target, context = t + if isinstance(target, Instance): # lambda object + target, context = None, None else: target, context = None, None @@ -1188,7 +1193,7 @@ # Test for NotImplemented. # Don't actually raise an exception. - self.new_op(TestIdentityAddress(self.get_builtin("NotImplemented", node))) + self.new_op(TestIdentityAddress(self.get_predefined_constant("NotImplemented"))) self.new_op(JumpIfTrue(next_method_block)) self.new_op(Jump(end_block)) @@ -1523,8 +1528,8 @@ def visitListCompIf(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "ListCompIf") def visitName(self, node): - if node.name == "None": - const = self.module.constant_values[None] + if self.module.predefined_constants.has_key(node.name): + const = self.module.constant_values[self.module.predefined_constants[node.name]] self.new_op(LoadConst(const)) else: self._visitName(node, self.name_load_instructions) @@ -1642,6 +1647,8 @@ self.discard_temp(temp2) def visitClass(self, node): + if not node.unit.referenced: + return # Store the name. @@ -1664,6 +1671,8 @@ def visitFrom(self, node): pass def visitFunction(self, node): + if not node.unit.referenced and not node.unit.is_method(): + return # Only store the name when visiting this node from outside. diff -r 390c6b60cc04 -r a40a277b1332 micropython/data.py --- a/micropython/data.py Tue Oct 28 01:08:06 2008 +0100 +++ b/micropython/data.py Sat Nov 08 21:15:11 2008 +0100 @@ -64,6 +64,21 @@ self.global_namespace = global_namespace self.finalised = 0 + def __delitem__(self, name): + del self.namespace[name] + + def has_key(self, name): + return self.namespace.has_key(name) + + def keys(self): + return self.namespace.keys() + + def values(self): + return self.namespace.values() + + def items(self): + return self.namespace.items() + def __getitem__(self, name): return self.namespace[name] @@ -134,21 +149,6 @@ return None - def __delitem__(self, name): - del self.namespace[name] - - def has_key(self, name): - return self.namespace.has_key(name) - - def keys(self): - return self.namespace.keys() - - def values(self): - return self.namespace.values() - - def items(self): - return self.namespace.items() - def make_global(self, name): if not self.namespace.has_key(name): self.globals.add(name) @@ -218,6 +218,13 @@ self.assignments = assignments self.assignment_values = set() + def set_referenced(self): + + "Indicate that the contents are referenced via a namespace." + + for value in self.assignment_values: + value.set_referenced() + def update(self, value, single_assignment): """ @@ -301,11 +308,15 @@ def __init__(self): self.parent = None + self.referenced = 0 # Image generation details. self.location = None + def set_referenced(self): + self.referenced = 1 + def __repr__(self): return "Instance()" @@ -317,13 +328,15 @@ pass +# Data objects appearing in programs before run-time. + class Const(Constant, Instance): "A constant object with no context." def __init__(self, value): + Instance.__init__(self) self.value = value - self.parent = None def __repr__(self): if self.location is not None: @@ -359,6 +372,7 @@ self.name = name self.parent = parent self.astnode = node + self.referenced = 0 # Superclasses, descendants and attributes. @@ -394,6 +408,9 @@ self.local_usage = 0 self.all_local_usage = 0 + def set_referenced(self): + self.referenced = 1 + def __repr__(self): if self.location is not None: return "Class(%r, %s, location=%r)" % (self.name, shortrepr(self.parent), self.location) @@ -700,6 +717,7 @@ self.has_star = has_star self.has_dstar = has_dstar self.astnode = node + self.referenced = 0 # Initialise the positional names. @@ -736,6 +754,9 @@ self.local_usage = 0 self.all_local_usage = 0 + def set_referenced(self): + self.referenced = 1 + def _add_parameters(self, argnames): for name in argnames: if isinstance(name, tuple): @@ -867,6 +888,15 @@ self.name = name self.parent_name = parent_name self.parent = None + self.referenced = 0 + + self.descendants = set() + + def set_referenced(self): + self.referenced = 1 + + def add_descendant(self, cls): + self.descendants.add(cls) def all_class_attributes(self): return {} @@ -893,6 +923,7 @@ NamespaceDict.__init__(self, self) self.name = name self.parent = None + self.referenced = 0 # Original location details. @@ -917,6 +948,9 @@ self.local_usage = 0 self.all_local_usage = 0 + def set_referenced(self): + self.referenced = 1 + def full_name(self): return self.name diff -r 390c6b60cc04 -r a40a277b1332 micropython/inspect.py --- a/micropython/inspect.py Tue Oct 28 01:08:06 2008 +0100 +++ b/micropython/inspect.py Sat Nov 08 21:15:11 2008 +0100 @@ -85,6 +85,14 @@ capable of being used as an AST visitor. """ + predefined_constants = { + "None" : None, + "True" : True, + "False" : False, + "Ellipsis" : Ellipsis, + "NotImplemented" : NotImplemented + } + def __init__(self, name, importer): """ @@ -99,6 +107,7 @@ # Import machinery links. self.importer = importer + self.optimisations = importer.optimisations self.builtins = self.importer.modules.get("__builtins__") self.loaded = 0 @@ -106,6 +115,11 @@ self.constant_values = importer.constant_values + # Ensure the predefined constants. + + for name, value in self.predefined_constants.items(): + self._make_constant(value) + # Current expression state. self.expr = None @@ -135,7 +149,7 @@ all = self["__all__"] if isinstance(all, compiler.ast.List): for n in all.nodes: - self[n.value] = self.importer.add_module(self.name + "." + n.value) + self.store(n.value, self.importer.add_module(self.name + "." + n.value)) return processed def vacuum(self): @@ -143,14 +157,63 @@ "Vacuum the module namespace, removing unloaded module references." for name, value in self.items(): - if isinstance(value, Module) and not value.loaded: - del self[name] + + if isinstance(value, Attr): + attr_value = value.value + + # Remove non-loaded modules. + + if isinstance(attr_value, Module) and not attr_value.loaded: + del self[name] + + # Remove unreferenced names. + # NOTE: This, due to the nature of the referenced attribute, assumes + # NOTE: that only explicitly mentioned classes and functions are + # NOTE: employed in the final program. + + elif self.should_optimise_unused_objects(): + + # Only remove entries for classes and functions, not methods. + + for attr_value in value.assignment_values: + if (isinstance(attr_value, Function) and not attr_value.is_method() or + isinstance(attr_value, Class)) and not attr_value.referenced: + pass + else: + break + else: + del self[name] # Complain about globals not initialised at the module level. - if isinstance(value, Global): + elif isinstance(value, Global): print "Warning: global %r in module %r not initialised at the module level." % (name, self.name) + # Remove unreferenced objects. + + if self.should_optimise_unused_objects(): + + all_objects = list(self.all_objects) + + for obj in all_objects: + if not obj.referenced: + self.all_objects.remove(obj) + + def add_object(self, obj, any_scope=0): + + """ + Record 'obj' if non-local or if the optional 'any_scope' is set to a + true value. + """ + + if any_scope or not (self.namespaces and isinstance(self.namespaces[-1], Function)): + self.all_objects.add(obj) + + # Optimisation tests. + + def should_optimise_unused_objects(self): + return "unused_objects" in self.optimisations + # Namespace methods. def store(self, name, obj): @@ -162,16 +225,11 @@ else: self.namespaces[-1].set(name, obj, not self.in_loop) - # Record all non-local objects. - - if not (self.namespaces and isinstance(self.namespaces[-1], Function)): - self.all_objects.add(obj) - def store_lambda(self, obj): "Store a lambda function 'obj'." - self.all_objects.add(obj) + self.add_object(obj) def store_module_attr(self, name, module): @@ -300,9 +358,21 @@ self.store(name, function) else: self.store_lambda(function) + + # Lambda functions are always assumed to be referenced. This is + # because other means of discovering the referencing of objects rely + # on the original names inherent in the definition of those objects. + + function.set_referenced() + + # Where defaults exist, an instance needs creating. Thus, it makes + # no sense to return a reference to the function here, since the + # recipient will not be referencing the function itself. + if node.defaults: - return None # NOTE: See lambda code in the ast module. + return Instance() # indicates no known target + self.add_object(function, any_scope=1) return function visitAdd = OP @@ -396,6 +466,7 @@ # Make an entry for the class. self.store(node.name, cls) + self.add_object(cls) # Process the class body. @@ -437,6 +508,9 @@ def visitFrom(self, node): module = self.importer.load(node.modname, 1) + if module is not None: + module.set_referenced() + #if module is None: # print "Warning:", node.modname, "not imported." @@ -445,8 +519,8 @@ if module is not None and module.namespace.has_key(name): attr = module[name] self.store(alias or name, attr.value) - if isinstance(attr, Module) and not attr.loaded: - self.importer.load(attr.name) + if isinstance(attr.value, Module) and not attr.value.loaded: + self.importer.load(attr.value.name) # Support the import of names from missing modules. @@ -457,8 +531,8 @@ for n in module.namespace.keys(): attr = module[n] self.store(n, attr.value) - if isinstance(attr, Module) and not attr.loaded: - self.importer.load(attr.name) + if isinstance(attr.value, Module) and not attr.value.loaded: + self.importer.load(attr.value.name) return None @@ -478,15 +552,20 @@ if isinstance(expr, Attr): value = expr.value if isinstance(value, (Class, Module)): - return value.namespace.get(node.attrname) + attr = value.namespace.get(node.attrname) elif isinstance(value, UnresolvedName): - return UnresolvedName(node.attrname, value.full_name(), self) + attr = UnresolvedName(node.attrname, value.full_name(), self) else: - return None - if self.builtins is not None: - return self.builtins.get(node.attrname) + attr = None + elif self.builtins is not None: + attr = self.builtins.get(node.attrname) else: - return UnresolvedName(node.attrname, value.full_name(), self) + attr = UnresolvedName(node.attrname, value.full_name(), self) + + if attr is not None: + attr.set_referenced() + + return attr def visitGlobal(self, node): if self.namespaces: @@ -510,9 +589,12 @@ def visitImport(self, node): for name, alias in node.names: if alias is not None: - self.store(alias, self.importer.load(name, 1) or UnresolvedName(None, name, self)) + module = self.importer.load(name, 1) or UnresolvedName(None, name, self) + self.store(alias, module) else: - self.store(name.split(".")[0], self.importer.load(name) or UnresolvedName(None, name.split(".")[0], self)) + module = self.importer.load(name) or UnresolvedName(None, name.split(".")[0], self) + self.store(name.split(".")[0], module) + module.set_referenced() return None @@ -550,16 +632,21 @@ def visitName(self, node): name = node.name - if name == "None": - return self._make_constant(None) + if self.predefined_constants.has_key(name): + attr = self._make_constant(self.predefined_constants[name]) elif self.namespaces and self.namespaces[-1].has_key(name): - return self.namespaces[-1][name] + attr = self.namespaces[-1][name] elif self.has_key(name): - return self[name] + attr = self[name] elif self.builtins is not None and self.builtins.has_key(name): - return self.builtins[name] + attr = self.builtins[name] else: - return None + attr = None + + if attr is not None: + attr.set_referenced() + + return attr visitNot = OP diff -r 390c6b60cc04 -r a40a277b1332 micropython/opt.py --- a/micropython/opt.py Tue Oct 28 01:08:06 2008 +0100 +++ b/micropython/opt.py Sat Nov 08 21:15:11 2008 +0100 @@ -28,8 +28,11 @@ "A code optimiser." supported_optimisations = [ + # Code generation optimisations: "constant_storage", "constant_accessor", "known_target", "self_access", - "temp_storage", "load_operations", "no_operations", "unused_results" + "temp_storage", "load_operations", "no_operations", "unused_results", + # Inspection optimisations: + "unused_objects" ] def __init__(self, translation, optimisations=None): diff -r 390c6b60cc04 -r a40a277b1332 test.py --- a/test.py Tue Oct 28 01:08:06 2008 +0100 +++ b/test.py Sat Nov 08 21:15:11 2008 +0100 @@ -9,14 +9,13 @@ code = None -def show(importer, with_builtins=0, optimisations=None): - make(importer, with_builtins, optimisations) +def show(importer, with_builtins=0): + make(importer, with_builtins) show_code(code) -def make(importer, with_builtins=0, optimisations=None): - optimisations = optimisations or requested_optimisations +def make(importer, with_builtins=0): global code - code = importer.get_image(with_builtins, optimisations) + code = importer.get_image(with_builtins) def show_code(code): for i, x in enumerate(code): @@ -28,9 +27,9 @@ print "%6d" % (len(table_slice) - table_slice.count(None)), \ "".join(entry and "#" or "_" for entry in table_slice) -def machine(importer, with_builtins=0, optimisations=None, debug=0): +def machine(importer, with_builtins=0, debug=0): print "Making the image..." - make(importer, with_builtins, optimisations) + make(importer, with_builtins) print "Getting raw structures..." ot = importer.get_object_table() pt = importer.get_parameter_table() @@ -59,10 +58,8 @@ else: program = None - i = micropython.Importer(path, "-v" in args) - if "-omax" in args: - requested_optimisations = i.supported_optimisations + requested_optimisations = micropython.Importer.supported_optimisations else: requested_optimisations = [] for arg in args: @@ -70,6 +67,8 @@ for arg_part in arg[2:].split(","): requested_optimisations.append(arg_part) + i = micropython.Importer(path, requested_optimisations, "-v" in args) + try: builtins = i.load_from_file("lib/builtins.py", "__builtins__") if program is None: