# HG changeset patch # User Paul Boddie # Date 1266885051 -3600 # Node ID 213b40328a64087ea646e9c9482b8d1f0f7b4954 # Parent 7dc22ce269e10f72db404212136c484975ce60f8 Simplified the usage tracking by merely recording active users (providers) of names and propagating usage back to them. Accesses retain lists of active users and the name of the object through which an access is performed. To generate specific access instructions, the users are consulted for their usage lists and possible types deduced. Similarly, guards are generated by deducing possible types from such usage lists. diff -r 7dc22ce269e1 -r 213b40328a64 micropython/data.py --- a/micropython/data.py Sun Feb 21 22:26:08 2010 +0100 +++ b/micropython/data.py Tue Feb 23 01:30:51 2010 +0100 @@ -131,33 +131,14 @@ # Specific namespaces should define known names during initialisation. # For example, functions can define names belonging to parameters. - # Attribute usage, defining a consensus for each name. - - self.attributes_used = [{}] # stack of usage - self.attribute_shelves = [] # stack of unmerged definitions - - # Attribute usage abandonment, where the usage will not contribute to - # the consensus. - - self.abandon_attributes = 0 # used when a block will never contribute - - # Speculative attribute usage where names may not contribute to a - # consensus beyond a branch, but where the usage will still influence - # acceptable types for a name. - - self.speculative_attributes = [{}] # stack of speculative usage - self.speculative_shelves = [] # stack of unmerged speculative definitions - # Attribute users, defining names which use attributes. self.attribute_users = [{}] # stack of assignments - self.all_attribute_users = [{}] # stack of assignments (to record any usage) self.user_shelves = [] # Define attribute usage to identify active program sections. - self.all_usage_shelves = [] # stack of unmerged coverage-related definitions - self.all_attributes_used = [] + self.all_attribute_users = set() # Attribute/name definition and access. @@ -328,8 +309,9 @@ """ usage = set() - for names in self.all_attributes_used: - usage.add(tuple(names)) + for user in self.all_attribute_users: + for name, attrnames in user._attrnames.items(): + usage.add(tuple(attrnames)) return usage def use_attribute(self, name, attrname): @@ -348,25 +330,16 @@ with the given 'attrname'. """ - defs = self.attributes_used[-1] users = self.attribute_users[-1] - # Permit the unforeseen definition of names since some names are likely - # to be defined by things (such as class definitions) which will not - # require access optimisations, but which still need to be monitored. - - if not defs.has_key(name): - defs[name] = set() - - defs[name].add(attrname) - # Add the usage to all current users. if users.has_key(name): for user in users[name]: user._attrnames[name].add(attrname) - - return defs[name] + return users[name] + else: + return [] def _define_attribute_user(self, node): @@ -382,41 +355,22 @@ "Define 'node' as the user of attributes for the given 'name'." - defs = self.attributes_used[-1] users = self.attribute_users[-1] - all_users = self.all_attribute_users[-1] - speculative = self.speculative_attributes[-1] - - # Record the current name usage as speculative since it will not be - # propagated any further. - - if not speculative.has_key(name): - speculative[name] = defs.get(name, set()) - - # Where speculative usage has already been recorded, just note the usage - # for coverage purposes. - - else: - self.all_usage_shelves[-1].append({name : defs[name]}) # This node overrides previous definitions. - all_users[name] = set([node]) users[name] = set([node]) - defs[name] = set() # Record the attribute combinations for the name. if not hasattr(node, "_attrnames"): node._attrnames = {} - node._alternative_attrnames = {} node._attrnames[name] = set() - node._alternative_attrnames[name] = set() - # Remember all attribute combinations. + # Remember this user. - self.all_attributes_used.append(defs[name]) + self.all_attribute_users.add(node) def _new_branchpoint(self): @@ -425,9 +379,6 @@ and subsequently converge. """ - self.attribute_shelves.append([]) - self.speculative_shelves.append([]) - self.all_usage_shelves.append([]) self.user_shelves.append([]) def _new_branch(self): @@ -437,28 +388,14 @@ the new branch so that it may be augmented for each name locally. """ - d = {} - for name, attrnames in self.attributes_used[-1].items(): - d[name] = set(attrnames) - self.attributes_used.append(d) - - # In the new branch, usage does not necessarily feed back to the users - # immediately. - - self.attribute_users.append({}) - - # Retain a record of all active users. + # Retain a record of active users. d = {} - d.update(self.all_attribute_users[-1]) - self.all_attribute_users.append(d) - - # Speculative attributes are recorded for subsequent feedback to users. - - self.speculative_attributes.append({}) + d.update(self.attribute_users[-1]) + self.attribute_users.append(d) def _abandon_branch(self): - self.abandon_attributes = 1 + pass def _shelve_branch(self): @@ -469,137 +406,49 @@ observations after a merge. """ - usage = self.attributes_used.pop() - speculative = self.speculative_attributes.pop() - - # Record contributing usage. - - if not self.abandon_attributes: - self.attribute_shelves[-1].append(usage) - - # Record all usage (for coverage). - - self.all_usage_shelves[-1].append(usage) - - # Record speculative usage. - - if self.abandon_attributes: - for name, attrnames in usage.items(): - if not speculative.has_key(name): - speculative[name] = attrnames - - self.speculative_shelves[-1].append(speculative) - - # NOTE: Could record contributing usage as speculative usage. - - #self.speculative_shelves[-1].append(usage) - - # Forget about any nodes which defined names employing attributes in - # this branch if the branch is abandoned. - users = self.attribute_users.pop() - - if not self.abandon_attributes: - self.user_shelves[-1].append(users) - - self.all_attribute_users.pop() - self.abandon_attributes = 0 + self.user_shelves[-1].append(users) def _merge_branches(self): """ - Merge control-flow branches. This should find the intersection of the - usage contributions from each branch, which have been "shelved", and - update the active usage dictionary with these contributions. - - Where branches are "abandoned", their attribute usage will not affect - the subsequent usage observations, but such usage will be recorded in - order to deduce function usage. + Merge control-flow branches. This should find the users active within + each branch, which have been "shelved", and update the active users + dictionary with these contributions. """ - # The active dictionary holds the usage for names defined before the - # branches. The users dictionary holds the active users defining each - # name. - - active = self.attributes_used[-1] - users = self.attribute_users[-1] - all_users = self.all_attribute_users[-1] - speculative = self.speculative_attributes[-1] - - # Take each alternative branch, currently shelved, and find the - # intersection of their contributions for each name. - - # Where branches contribute attribute usage observations, process these - # as described above. Otherwise, preserve the previous observations. - - shelved_defs = self.attribute_shelves.pop() - - if shelved_defs: - defs = dict(shelved_defs[0]) - - for next_defs in shelved_defs[1:]: - for name, attrnames in next_defs.items(): - if defs.has_key(name): - defs[name] = defs[name].intersection(attrnames) - - # Intersect the contributions with the previous state for each name. - - for name, attrnames in defs.items(): - if active.has_key(name): - active[name].intersection_update(attrnames) - else: - active[name] = attrnames - - # Feed speculative definitions back to the users previously known. - - speculative_defs = self.speculative_shelves.pop() - - if speculative_defs: - for defs in speculative_defs: - for name, attrnames in defs.items(): - - # Where users are active for a name, produce alternatives. - - if all_users.has_key(name): - for node in all_users[name]: - - # Add the usage to the alternatives. - - if not node._alternative_attrnames.has_key(name): - node._alternative_attrnames[name] = set([tuple(attrnames)]) - else: - node._alternative_attrnames[name].add(tuple(attrnames)) - # Combine the attribute users. This ensures that a list of users # affected by attribute usage is maintained for the current branch. - for shelved_users in self.user_shelves.pop(): - for name, nodes in shelved_users.items(): + users = self.attribute_users[-1] + new_users = {} - # Handle cases where the name is not known at this level. + all_shelved_users = self.user_shelves.pop() + all_user_names = set() - if users.has_key(name): - users[name].update(nodes) - else: - users[name] = nodes + # Find all the names defined by the branches. - # Where each shelved set of definitions is a superset of the eventual - # definitions for a name, record these specialised sets of usage. + for shelved_users in all_shelved_users: + all_user_names.update(shelved_users.keys()) + + # Copy all definitions from the branches for the names, maintaining + # the existing users where a branch does not redefine a name. - # Note that abandoned definitions contribute to sets of usage, since - # although they do not contribute to further usage in a namespace, any - # attribute combinations do indicate function usage. + for shelved_users in all_shelved_users: + for name in all_user_names: - all_usage_defs = self.all_usage_shelves.pop() + if shelved_users.has_key(name): + nodes = shelved_users[name] + else: + nodes = users.get(name, set()) - for defs in all_usage_defs: - for name, attrnames in defs.items(): + if nodes: + if not new_users.has_key(name): + new_users[name] = nodes + else: + new_users[name].update(nodes) - # Check for isolated pockets of attribute usage as well as more - # specific usage. - - if not active.has_key(name) or attrnames.issuperset(active[name]): - self.all_attributes_used.append(attrnames) + self.attribute_users[-1] = new_users # Program data structures. diff -r 7dc22ce269e1 -r 213b40328a64 micropython/inspect.py --- a/micropython/inspect.py Sun Feb 21 22:26:08 2010 +0100 +++ b/micropython/inspect.py Tue Feb 23 01:30:51 2010 +0100 @@ -497,7 +497,8 @@ # Note usage of the attribute where a local is involved. if expr.parent is self.get_namespace(): - node._attrnames = self.use_attribute(expr.name, node.attrname) + node._attrusers = self.use_attribute(expr.name, node.attrname) + node._username = expr.name return None @@ -754,7 +755,8 @@ # Note usage of the attribute where a local is involved. if expr.parent is self.get_namespace(): - node._attrnames = self.use_attribute(expr.name, attrname) + node._attrusers = self.use_attribute(expr.name, attrname) + node._username = expr.name else: self.use_name(attrname) diff -r 7dc22ce269e1 -r 213b40328a64 micropython/trans.py --- a/micropython/trans.py Sun Feb 21 22:26:08 2010 +0100 +++ b/micropython/trans.py Tue Feb 23 01:30:51 2010 +0100 @@ -315,37 +315,13 @@ for name, names_used in node._attrnames.items(): - # Consider alternatives. - - if node._alternative_attrnames.has_key(name): - all_names_used = set() - all_names_used.update(node._alternative_attrnames[name]) - all_names_used.add(tuple(names_used)) - else: - all_names_used = [names_used] - # Get the names of all object types supporting these names. - targets = set() - common_targets = None - - for names_used in all_names_used: - found_targets = self.objtable.all_possible_objects_plus_status(names_used) - found_target_names = [target_name for (target_name, is_static) in found_targets] - targets.update(found_targets) - - if common_targets is None: - common_targets = set(found_target_names) - else: - common_targets.intersection_update(found_target_names) - - # Report cases where no common targets can be found. - - if not common_targets: - raise TranslateError(self.module.full_name(), node, "No common types found for expected attribute usage.") + targets = self.objtable.all_possible_objects_plus_status(names_used) + #found_target_names = [target_name for (target_name, is_static) in targets] # NOTE: Need to merge targets using the same type but suggesting - # NOTE: different kinds of attributes. + # NOTE: different kinds of attributes (instance vs. class). # Where only one object type is suggested, produce a guard. # NOTE: This only supports classes as types, not modules. @@ -534,16 +510,17 @@ # Attempt to deduce the target of an attribute access by searching for a # unique type providing the names associated with the accessed object. - # NOTE: This should re-use type information defined at assignment - # NOTE: locations. elif self.optimiser.should_optimise_accesses_by_attribute_usage(): - if hasattr(node, "_attrnames"): - target_names = self.objtable.all_possible_objects(node._attrnames) + if hasattr(node, "_attrusers"): + target_names = set() + + for user in node._attrusers: + target_names.update(self.objtable.all_possible_objects(user._attrnames[node._username])) if len(target_names) == 1: - target_name = target_names[0] + target_name = list(target_names)[0] # Access the object table to get the attribute.