I'm a bit disorganized here, but I don't think delaying will help much as my brain is turning to mush. Nothing ventured...
Notes for description of value annotator Iterative. Allows examination of individual steps Stable. Produces result in finite amount of time Order Insensitive. Always produces the same result, no matter what order in which it processes the sourcecode Specialization of builtins. All functions are given a "space depth". Multiple calls (at different lines of code) to the same function will, if it has a deeper depth, create separate copies of the function in their own "space". If those functions then call a function of a shallower depth they will use a shared function (rather than continuing to specialize it). The result is that separate calls to builtin functions (such as the plus operator) will get separate annotations, but without risk of an infinite loop in the annotation process. Values. A Value is a set (in the mathematical sense) of possible values, be they integer, float, string, or whatever. In practice it must store an approximation so that a set of 0..2**64-1 can be represented. It is acceptable for the set to be expanded to include values that are not really possible (as the program will still behave correctly), but not acceptable to be smaller. Note however that as an iterative process is used to determine values, it will initially be to small, and later replaced with new Values that cover the full range. Hypothetical value expansions. A mechanism is needed to expand values to their full range quickly, rather than iterate it one step at a time. To do this an integer_add will notice on the second pass (not the first!) that it had a previous possible output, and that the new output appears to create a sequence from it. A new value set is created as normal (increased by only a single step), except a "hypothetical" part is added to it. The hypothetical contains a Value set with the predicted sequence of values (not including any already known), as well as a reference to the node/space that created it. The value is then set as the new output for the integer_add node and is propagated through the rest of the code. Other nodes will modify the hypothetical as if it was a normal value set, including putting a cap on the the highest value in the case of an if branch, but they will not explore new code as a result of it. If the hypothetical reaches the node/space that created it then this indicates there is a loop which allows the value to expand over the whole range, and the node will convert it into a normal value (including any caps that were discovered). Branches and bool replacement Values. To effect a cap on the range of a value the bool value produced by lessthan and similar operations will contain a pair reduced Value associated with the input variables. If the bool is used for a branch then either the "True" or "False" version of the reduced Value associated with the bool's original input variable will be used to replace the variable thereafter. Note that a form of Single Static Assignment is used to allow a variable to have different values at different points in a function. Comment on SSA and aliases. As the branch that reduces a variable's range may happen outside the function itself, it is necessary to make the SSA alias lists globally available and allow modification at any point. This means they must be copied to every node, with the resulting cost being quadratic (O(n**2)). However, as most of the copies would have identical contents I believe it would be possible to optimize this and get performance that is closer to linear (O(n)). Finally, a note on what sorts of code this is aimed at. Anything where all the code can be determined at compiletime, ie no eval/exec/__import__/reload. Some analysis of code that does use those features would still be possible however. Spaces diagram: http://members.shaw.ca/rhamph/python-annvalue/spaces.pdf Values diagram: http://members.shaw.ca/rhamph/python-annvalue/values.pdf Partially annotated test "program": http://members.shaw.ca/rhamph/python-annvalue/annotation.pdf My sourcecode (requires autopath.py): http://members.shaw.ca/rhamph/python-annvalue/basicblock.py -- Adam Olsen, aka Rhamphoryncus _______________________________________________ [email protected] http://codespeak.net/mailman/listinfo/pypy-dev
