Optimisations

=============

Some optimisations around constant objects might be possible; these depend on

the following:

  * Reliable tracking of assignments: where assignment operations occur, the

    target of the assignment should be determined if any hope of optimisation

    is to be maintained. Where no guarantees can be made about the target of

    an assignment, no assignment-related information should be written to

    potential targets.

  * Objects acting as "containers" of attributes must be regarded as "safe":

    where assignments are recorded as occurring on an attribute, it must be

    guaranteed that no other unforeseen ways exist to assign to such

    attributes.

The discussion below presents certain rules which must be imposed to uphold

the above requirements.

Safe Containers

---------------

Where attributes of modules, classes and instances are only set once and are

effectively constant, it should be possible to circumvent the attribute lookup

mechanism and to directly reference the attribute value. This technique may

only be considered applicable for the following "container" objects, subject

to the noted constraints:

 1. For modules, "safety" is enforced by ensuring that assignments to module

    attributes are only permitted within the module itself either at the

    top-level or via names declared as globals. Thus, the following would not

    be permitted:

    another_module.this_module.attr = value

    In the above, this_module is a reference to the current module.

    Where assignments to module attributes are permitted from outside a

    module, modules can no longer be relied upon to provide constant attribute

    values, even if a cursory inspection of module-level code would suggest

    that some attributes are effectively constant.

 2. For classes, "safety" is enforced by ensuring that assignments to class

    attributes are only permitted within the class definition, outside

    methods. This would mean that classes would be "sealed" at definition time

    (like functions).

Unlike the property of function locals that they may only sensibly be accessed

within the function in which they reside, these cases demand additional

controls or assumptions on or about access to the stored data. Meanwhile, it

would be difficult to detect eligible attributes on arbitrary instances due to

the need for some kind of type inference or abstract execution.

Constant Attributes

-------------------

When accessed via "safe containers", as described above, any attribute with

only one recorded assignment on it can be considered a constant attribute and

this eligible for optimisation, the consequence of which would be the

replacement of a LoadAttrIndex instruction (which needs to look up an

attribute using the run-time details of the "container" and the compile-time

details of the attribute) with a LoadAttr instruction.

However, some restrictions exist on assignment operations which may be

regarded to cause only one assignment in the lifetime of a program:

 1. For module attributes, only assignments at the top-level outside loop

    statements can be reliably assumed to cause only a single assignment.

 2. For class attributes, only assignments at the top-level within class

    definitions and outside loop statements can be reliably assumed to cause

    only a single assignment.

All assignments satisfying the "safe container" requirements, but not the

requirements immediately above, should each be recorded as causing at least

one assignment.

Additional Controls

-------------------

For the above cases for "container" objects, the following controls would need

to apply:

 1. Modules would need to be immutable after initialisation. However, during

    initialisation, there remains a possibility of another module attempting

    to access the original module. For example, if ppp/__init__.py contained

    the following...

    x = 1

    import ppp.qqq

    print x

    ...and if ppp/qqq.py contained the following...

    import ppp

    ppp.x = 2

    ...then the value 2 would be printed. Since modules are objects which are

    registered globally in a program, it would be possible to set attributes

    in the above way.

 2. Classes would need to be immutable after initialisation. However, since

    classes are objects, any reference to a class after initialisation could

    be used to set attributes on the class.

Solutions:

 1. Insist on global scope for module attribute assignments.

 2. Insist on local scope within classes.

Both of the above measures need to be enforced at run-time, since an arbitrary

attribute assignment could be attempted on any kind of object, yet to uphold

the properties of "safe containers", attempts to change attributes of such

objects should be denied. Since foreseen attribute assignment operations have

certain properties detectable at compile-time, it could be appropriate to

generate special instructions (or modified instructions) during the

initialisation of modules and classes for such foreseen assignments, whilst

employing normal attribute assignment operations in all other cases. Indeed,

the StoreAttr instruction, which is used to set attributes in "safe

containers" would be used exclusively for this purpose; the StoreAttrIndex

instruction would be used exclusively for all other attribute assignments.

To ensure the "sealing" of modules and classes, entries in the attribute

lookup table would encode whether a class or module is being accessed, so

that the StoreAttrIndex instruction could reject such accesses.

Constant Attribute Values

-------------------------

Where an attribute value is itself regarded as constant, is a "safe container"

and is used in an operation accessing its own attributes, the value can be

directly inspected for optimisations or employed in the generated code. For

the attribute values themselves, only objects of a constant nature may be

considered suitable for this particular optimisation:

  * Classes

  * Modules

  * Instances defined as constant literals

This is because arbitrary objects (such as most instances) have no

well-defined form before run-time and cannot be investigated further at

compile-time or have a representation inserted into the generated code.

Class Attributes and Access via Instances

-----------------------------------------

Unlike module attributes, class attributes can be accessed in a number of

different ways:

  * Using the class itself:

    C.x = 123

    cls = C; cls.x = 234

  * Using a subclass of the class (for reading attributes):

    class D(C):

        pass

    D.x # setting D.x would populate D, not C

  * Using instances of the class or a subclass of the class (for reading

    attributes):

    c = C()

    c.x # setting c.x would populate c, not C

Since assignments are only achieved using direct references to the class, and

since class attributes should be defined only within the class initialisation

process, the properties of class attributes should be consistent with those

desired.

Method Access via Instances

---------------------------

It is desirable to optimise method access, even though most method calls are

likely to occur via instances. It is possible, given the properties of methods

as class attributes to investigate the kind of instance that the self

parameter/local refers to within each method: it should be an instance either

of the class in which the method is defined or a compatible class, although

situations exist where this might not be the case:

  * Explicit invocation of a method:

    d = D() # D is not related to C

    C.f(d) # calling f(self) in C

If blatant usage of incompatible instances were somehow disallowed, it would

still be necessary to investigate the properties of an instance's class and

its relationship with other classes. Consider the following example:

    class A:

        def f(self): ...

    class B:

        def f(self): ...

        def g(self):

            self.f()

    class C(A, B):

        pass

Here, instances of B passed into the method B.g could be assumed to provide

access to B.f when self.f is resolved at compile-time. However, instances of C

passed into B.g would instead provide access to A.f when self.f is resolved at

compile-time (since the method resolution order is C, A, B instead of just B).

One solution might be to specialise methods for each instance type, but this

could be costly. Another less ambitious solution might only involve the

optimisation of such internal method calls if an unambiguous target can be

resolved.

Narrowing Type Candidates using Attribute Names

-----------------------------------------------

Within functions, it might be useful to record attribute accesses on local

names and to collect the names in order to help resolve targets in the

generated code. For example:

    def f(x, y):

        x.method(y)

        if x.something:

            ...

        return x.attr

Here, the object referenced via x should have "method", "something" and "attr"

as attributes. We could impose a test for a type providing these attributes at

the earliest opportunity and then specialise the attribute accesses, perhaps

also invocations, in the generated code. AttributeError occurrences would need

to be considered, however, potentially disqualifying certain attributes from

any optimisations, and control flow would also need to be considered. The

result would resemble the following:

    def f(x, y):

        if not isinstance(x, C) and x is not C:

            raise TypeError

        x.method(y)

        if x.something:

            ...

        return x.attr

With more specific information about the attributes used with a given name,

combinations of attributes can be provided instead of single attributes when

recording attribute usage. For example, from the above:

    x uses method    -> indicates potential usage of C.method, D1.method, ...

    x uses something -> indicates potential usage of C.something,

                        D2.something, ...

    x uses attr      -> indicates potential usage of C.attr, D3.attr, ...

These unspecific declarations of attribute usage can be replaced with the

following:

    x uses method, something, attr -> indicates potential usage of C, D4, ...

                                      (each providing all of the stated

                                      attributes)

Reducing Object Table Scope

---------------------------

Where attributes may be used in a program but never accessed via the object

table-dependent instructions, such attributes could be omitted from the object

table.

Implemented Optimisation Types

==============================

Optimisation                    Prerequisites and Effect

------------                    ------------------------

constant_storage                value instruction references a constant;

(guidance)                      storage instruction references a constant;

                              | indicate whether both instructions satisfy the

                              | preconditions and should be removed/omitted

constant_accessor               value instruction references a constant;

(guidance)                    | target name provided (for use in producing an

                              | address access instruction)

known_target                    value instruction references a constant;

(guidance)                    | target and context are provided (no instructions

                              | are removed)

self_access                     value instruction references "self" in a method;

(guidance)                      specified attribute name always has the same

                                position;

                              | indicate whether an appropriate instruction can

                              | be generated for the access

temp_storage                    value instruction is a simple input operation;

(elimination)                   value instruction is the last instruction;

(guidance)                    | remove the value instruction, provide the value

                              | instruction in place of a temporary storage

                              | reference

no_operations                   input to the current instruction loads from the

(guidance)                      destination of the current instruction;

                              | indicate that the current instruction should be

                              | omitted

unused_results                  value instruction is a simple input operation;

(elimination)                   value instruction is the final instruction of a

                                discarded expression;

                              | remove the value instruction

unused_objects                  attribute is defined using a name which is not

(inspection)                    used in an active region of the program or is

                                defined within a class which is not used by

                                the program, object is unambiguously

                                referenced by such attributes

                              | remove such attributes and objects