On Mon, Feb 14, 2011 at 9:49 PM, Vitja Makarov <vitja.makarov@gmail.com> wrote:
2011/2/15 Robert Bradshaw <robertwb@math.washington.edu>:
On Sun, Feb 13, 2011 at 11:40 PM, Vitja Makarov <vitja.makarov@gmail.com> wrote:
Hi!
In order to implement "reaching definitions" algorithm. I'm now working on control-flow (or data-flow) graph.
Here is funny picture made with graphviz ;)
http://piccy.info/view3/1099337/ca29d7054d09bd0503cefa25f5f49420/1200/
Cool. Any plans on handling exceptions?
Sure, but I don't have much time for this :(
Linear block inside try...except body should be split by assignments and each subblock should point to exception handling entry point.
Would every possible failing sub-expression have to point to the exception handling point(s)? I suppose it depends on whether you'll be handling more than assignment tracking.
As result I want to have set of possible assignments for each NameNode position.
So handling of uninitialized variables, unused, unused results should be easy, later it may help to implement local variable deletion. And guess that could help type inference.
Ye. - Robert
Robert Bradshaw, 15.02.2011 08:21:
On Mon, Feb 14, 2011 at 9:49 PM, Vitja Makarov wrote:
2011/2/15 Robert Bradshaw:
On Sun, Feb 13, 2011 at 11:40 PM, Vitja Makarov wrote:
Hi!
In order to implement "reaching definitions" algorithm. I'm now working on control-flow (or data-flow) graph.
Here is funny picture made with graphviz ;)
http://piccy.info/view3/1099337/ca29d7054d09bd0503cefa25f5f49420/1200/
Cool. Any plans on handling exceptions?
Sure, but I don't have much time for this :(
Linear block inside try...except body should be split by assignments and each subblock should point to exception handling entry point.
Would every possible failing sub-expression have to point to the exception handling point(s)?
Well, in most cases (especially the interesting ones), this will be the function exit point, so it'll be easy. And in some cases, we may be able to infer that a specific exception that an expression (e.g. arithmetics or a 'raise' statement) can raise will not get caught by a given except clause (although that's certainly a tricky optimisation). But in general, I think any subexpression that potentially raises an exception must point to the next exception handling point.
I suppose it depends on whether you'll be handling more than assignment tracking.
We *may* get away with a statement-level graph in that case, but I somehow doubt it already. For example, list comprehensions leak their variable in Py2 code, so it's important to know if they are executed or not, and they may appear in any kind of expression. Stefan
2011/2/15 Stefan Behnel <stefan_ml@behnel.de>:
Robert Bradshaw, 15.02.2011 08:21:
On Mon, Feb 14, 2011 at 9:49 PM, Vitja Makarov wrote:
2011/2/15 Robert Bradshaw:
On Sun, Feb 13, 2011 at 11:40 PM, Vitja Makarov wrote:
Hi!
In order to implement "reaching definitions" algorithm. I'm now working on control-flow (or data-flow) graph.
Here is funny picture made with graphviz ;)
http://piccy.info/view3/1099337/ca29d7054d09bd0503cefa25f5f49420/1200/
Cool. Any plans on handling exceptions?
Sure, but I don't have much time for this :(
Linear block inside try...except body should be split by assignments and each subblock should point to exception handling entry point.
Would every possible failing sub-expression have to point to the exception handling point(s)?
Not sure here as now graph node is list of NameNode ref and AssignmentNode. I'm not sure but it seems that every sub-expression could raise exception now, is there any flag?
Well, in most cases (especially the interesting ones), this will be the function exit point, so it'll be easy. And in some cases, we may be able to infer that a specific exception that an expression (e.g. arithmetics or a 'raise' statement) can raise will not get caught by a given except clause (although that's certainly a tricky optimisation).
But in general, I think any subexpression that potentially raises an exception must point to the next exception handling point.
Right, and each exception handling point should have reference to the next one or function exit point.
I suppose it depends on whether you'll be handling more than assignment tracking.
We *may* get away with a statement-level graph in that case, but I somehow doubt it already. For example, list comprehensions leak their variable in Py2 code, so it's important to know if they are executed or not, and they may appear in any kind of expression.
This should be special case for scoped expression node. Now I build graph "from scratch" it include only name node references and assignments, and positions marks to draw gv. May be node tree should be translated into graph and then local variables graph could be created from it. On the other hand CreateAbstractGraph transformation could be used to create specialized graph. -- vitja.
2011/2/15 Stefan Behnel <stefan_ml@behnel.de>:
Robert Bradshaw, 15.02.2011 08:21:
On Mon, Feb 14, 2011 at 9:49 PM, Vitja Makarov wrote:
2011/2/15 Robert Bradshaw:
On Sun, Feb 13, 2011 at 11:40 PM, Vitja Makarov wrote:
Hi!
In order to implement "reaching definitions" algorithm. I'm now working on control-flow (or data-flow) graph.
Here is funny picture made with graphviz ;)
http://piccy.info/view3/1099337/ca29d7054d09bd0503cefa25f5f49420/1200/
Cool. Any plans on handling exceptions?
Sure, but I don't have much time for this :(
Linear block inside try...except body should be split by assignments and each subblock should point to exception handling entry point.
Would every possible failing sub-expression have to point to the exception handling point(s)?
Well, in most cases (especially the interesting ones), this will be the function exit point, so it'll be easy. And in some cases, we may be able to infer that a specific exception that an expression (e.g. arithmetics or a 'raise' statement) can raise will not get caught by a given except clause (although that's certainly a tricky optimisation).
But in general, I think any subexpression that potentially raises an exception must point to the next exception handling point.
I suppose it depends on whether you'll be handling more than assignment tracking.
We *may* get away with a statement-level graph in that case, but I somehow doubt it already. For example, list comprehensions leak their variable in Py2 code, so it's important to know if they are executed or not, and they may appear in any kind of expression.
Hmm... both python and codespeaks in the thread Here is my commit it's mostly broken now but anyway https://github.com/vitek/cython/commit/5579b23c3c1c06981331b6427a73e5cb19980... -- vitja.
2011/2/16 Vitja Makarov <vitja.makarov@gmail.com>:
2011/2/15 Stefan Behnel <stefan_ml@behnel.de>:
Robert Bradshaw, 15.02.2011 08:21:
On Mon, Feb 14, 2011 at 9:49 PM, Vitja Makarov wrote:
2011/2/15 Robert Bradshaw:
On Sun, Feb 13, 2011 at 11:40 PM, Vitja Makarov wrote:
Hi!
In order to implement "reaching definitions" algorithm. I'm now working on control-flow (or data-flow) graph.
Here is funny picture made with graphviz ;)
http://piccy.info/view3/1099337/ca29d7054d09bd0503cefa25f5f49420/1200/
Cool. Any plans on handling exceptions?
Sure, but I don't have much time for this :(
Linear block inside try...except body should be split by assignments and each subblock should point to exception handling entry point.
Would every possible failing sub-expression have to point to the exception handling point(s)?
Well, in most cases (especially the interesting ones), this will be the function exit point, so it'll be easy. And in some cases, we may be able to infer that a specific exception that an expression (e.g. arithmetics or a 'raise' statement) can raise will not get caught by a given except clause (although that's certainly a tricky optimisation).
But in general, I think any subexpression that potentially raises an exception must point to the next exception handling point.
I suppose it depends on whether you'll be handling more than assignment tracking.
We *may* get away with a statement-level graph in that case, but I somehow doubt it already. For example, list comprehensions leak their variable in Py2 code, so it's important to know if they are executed or not, and they may appear in any kind of expression.
Hmm... both python and codespeaks in the thread
Here is my commit it's mostly broken now but anyway https://github.com/vitek/cython/commit/5579b23c3c1c06981331b6427a73e5cb19980...
I've update stuff: - algo for finding definitions - warnings for uninitialized and may be uninitialised use - few test cases Trying to compile ParseTreeTransforms.py I've found this for example: warning: Cython/Compiler/ParseTreeTransforms.py:1182:27: Variable 'template' may be used uninitialized def create_Property(self, entry): if entry.visibility == 'public': if entry.type.is_pyobject: template = self.basic_pyobject_property else: template = self.basic_property elif entry.visibility == 'readonly': template = self.basic_property_ro property = template.substitute({ u"ATTR": ExprNodes.AttributeNode(pos=entry.pos, obj=ExprNodes.NameNode(pos=entry.pos, name="self"), attribute=entry.name), }, pos=entry.pos).stats[0] -- vitja.
Vitja Makarov, 20.02.2011 18:23:
2011/2/16 Vitja Makarov:
Hmm... both python and codespeaks in the thread
Yes, we should keep it to cython-devel only. Sorry for mixing it up.
Here is my commit it's mostly broken now but anyway https://github.com/vitek/cython/commit/5579b23c3c1c06981331b6427a73e5cb19980...
Flow control support is large enough to merit its own module. Not sure how 'smart' git is here, but you can always keep the history by explicitly copying ParseTreeTransforms.py to FlowControl.py and removing the unrelated sections from both files. You are duplicating some code from the type inferencer. We might want to clean that up at some point. However, given that flow control analysis will allow us to improve the type inferencer, I think it's best to keep this code in the FCA part.
I've update stuff: - algo for finding definitions - warnings for uninitialized and may be uninitialised use - few test cases
That looks very nice so far. Any idea how well it scales?
Trying to compile ParseTreeTransforms.py I've found this for example:
warning: Cython/Compiler/ParseTreeTransforms.py:1182:27: Variable 'template' may be used uninitialized
def create_Property(self, entry): if entry.visibility == 'public': if entry.type.is_pyobject: template = self.basic_pyobject_property else: template = self.basic_property elif entry.visibility == 'readonly': template = self.basic_property_ro property = template.substitute({ u"ATTR": ExprNodes.AttributeNode(pos=entry.pos,
obj=ExprNodes.NameNode(pos=entry.pos, name="self"), attribute=entry.name), }, pos=entry.pos).stats[0]
Ok, I guess that code generally works, but it's better to get rid of the code smell. Stefan
2011/2/22 Stefan Behnel <stefan_ml@behnel.de>:
Vitja Makarov, 20.02.2011 18:23:
2011/2/16 Vitja Makarov:
Hmm... both python and codespeaks in the thread
Yes, we should keep it to cython-devel only. Sorry for mixing it up.
Here is my commit it's mostly broken now but anyway
https://github.com/vitek/cython/commit/5579b23c3c1c06981331b6427a73e5cb19980...
Flow control support is large enough to merit its own module. Not sure how 'smart' git is here, but you can always keep the history by explicitly copying ParseTreeTransforms.py to FlowControl.py and removing the unrelated sections from both files.
Ok.
You are duplicating some code from the type inferencer. We might want to clean that up at some point. However, given that flow control analysis will allow us to improve the type inferencer, I think it's best to keep this code in the FCA part.
Yes, I think it could replace MarkAssignments transform later. Unreachable code could be delete there too.
I've update stuff: - algo for finding definitions - warnings for uninitialized and may be uninitialised use - few test cases
That looks very nice so far. Any idea how well it scales?
"Usually iterative algorithm takes no more then 5 iterations" For ExprNodes.py max number is 15 while avg is about 3 About execution time: ExprNodes.py compilation with c/f enabled takes 10.120 ms, w/o 9.325, ~10% slow down. -O flag could be introduced but I don't think that's a good idea. Should later try to execute cython compiled code.
Trying to compile ParseTreeTransforms.py I've found this for example:
warning: Cython/Compiler/ParseTreeTransforms.py:1182:27: Variable 'template' may be used uninitialized
def create_Property(self, entry): if entry.visibility == 'public': if entry.type.is_pyobject: template = self.basic_pyobject_property else: template = self.basic_property elif entry.visibility == 'readonly': template = self.basic_property_ro property = template.substitute({ u"ATTR": ExprNodes.AttributeNode(pos=entry.pos,
obj=ExprNodes.NameNode(pos=entry.pos, name="self"), attribute=entry.name), }, pos=entry.pos).stats[0]
Ok, I guess that code generally works, but it's better to get rid of the code smell.
Might be used warning should be disabled by default, because algorithm isn't smart enough: a = 1 if (a): b = 1 if (a): print b See also: http://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wuninitialized-... -- vitja.
On 02/15/2011 08:21 AM, Robert Bradshaw wrote:
On Mon, Feb 14, 2011 at 9:49 PM, Vitja Makarov<vitja.makarov@gmail.com> wrote:
2011/2/15 Robert Bradshaw<robertwb@math.washington.edu>:
On Sun, Feb 13, 2011 at 11:40 PM, Vitja Makarov<vitja.makarov@gmail.com> wrote:
Hi!
In order to implement "reaching definitions" algorithm. I'm now working on control-flow (or data-flow) graph.
Here is funny picture made with graphviz ;)
http://piccy.info/view3/1099337/ca29d7054d09bd0503cefa25f5f49420/1200/
Cool. Any plans on handling exceptions?
Sure, but I don't have much time for this :(
Linear block inside try...except body should be split by assignments and each subblock should point to exception handling entry point.
Would every possible failing sub-expression have to point to the exception handling point(s)? I suppose it depends on whether you'll be handling more than assignment tracking.
As result I want to have set of possible assignments for each NameNode position.
So handling of uninitialized variables, unused, unused results should be easy, later it may help to implement local variable deletion. And guess that could help type inference.
Ye.
I'm thinking that transforming NameNode + various assignment/lookup nodes into "opcode nodes" such as SetLocalNode, GetLocalNode, SetGlobalNode, GetAttributeNode and so on would be a natural step to make such code cleaner. Then (after an isolated transform doing this) the logic would just need to act on individual nodes, not combination of nodes. Just an idea. Dag Sverre
participants (4)
-
Dag Sverre Seljebotn -
Robert Bradshaw -
Stefan Behnel -
Vitja Makarov