Hi everyone,

I've still got pure functions on my books, and I've been looking around the node system that the compiler uses, especially pass 1. My main forte, which is probably also my weakness because I like going on wild goose chases, is looking for ways to optimise a process.  One thing I've noticed in the node pass is how often nodes are duplicated and destroyed, often without actually changing their contents, just their position in the tree.  For example, with the 'pass_1' and 'simplify' calls, things like "result := getcopy" in order to trigger another run of the pass, since the original always gets destroyed if result is not nil.

One solution I've found, that I'm researching the effectiveness of, is using a reference count system, and a method to mark a node as reused (internally, just raises the reference count).  There's still room for improvement though, as I've only gained a 1% speed gain in the compiler so far (while confirming that the compiled code doesn't change).  There are some hazards though, like when 'left' and 'right' are set to nil in order to prevent them from being destroyed (because the current node is due to be destroyed but is preserved due to a reference count greater than 1).

In the meantime, I've found and fixed a couple of memory leaks in the form of commands like "right:=right.simplify(false);" - besides assuming the result of 'simplify' is not nil, the original contents of 'right' is never freed and gets leaked.

This'll be something I'll be writing a design and implementation spec when I'm done, assuming I can get a worthwhile speed boost. More than anything I'm looking for ways make sure pure functions are processed as quickly as possible and improving compiler speed without sacrificing efficiency.

Gareth aka. Kit

Well, I haven't managed to get much of a saving yet, probably due to how good FPC's memory manager is as well as the "nf_pass1_done" flag that minimises needless parsing of the nodes even when they're copied.  Ultimately it's not worth showcasing just yet, although I might be able to pick out a couple of things like removing memory leaks, and avoiding the use of copying nodes does save on memory, which might be good for platforms that are a bit more constrained.

Either way, back to looking at pure functions again and seeing how well I can get the nodes down to just writing to the result and 'out' variables (the presence of 'Exit' tends to complicate things).

Gareth aka. Kit

If you use reference counting, how do you handle
1) node.location being different in pass 2 for identical nodes, since the result of nodes will often end up in different virtual registers
2) cases in the compiler where existing nodes are directly modified. This is mostly in ncnv, e.g. lines 2509 - 2511

While you are correct that the existing node juggling is error-prone in terms of memory leaks and other mistakes, I'm afraid reference counting may make it worse rather than better.

Jonas

Admittedly I haven't paid much attention to pass 2 yet, and the binary output of test programs, including Lazarus, shows that the generated binary is identical.  Granted, so far I haven't reached the point where I feel confident in reusing nodes because of things like directly modifying nodes as you describe (such as type conversions changing resultdefs).  Because my current time saving is only 1%, I'm putting this particular bit of exploration on the backburner - however, there are some things I can scavenge out of this that are useful:

- Fixing up "right:=right.simplify(False);", so it frees the original 'right' and raises an internal error if simplify's result is nil (since the code expects it not to be).
- Removing superfluous calls to "firstpass(result);" in some nodes' "pass_1" routines, since the routine that calls "pass_1" in the first place will automatically call "firstpass" on the result.  While it will exit immediately because the result node has already been processed, it is a waste of a call that increases stack depth.  In some cases, the extra call to "firstpass(result)" is justified - comments usually explain why - but if the routine exits immediately afterwards, it can be removed without harm.
- Constructs such as "result := getcopy;" being changed so it doesn't go through the wasteful process of creating a copy of the node tree at that point and deleting the original (which 'firstpass' automatically does if the result is not nil).  I introduced a method named "ProtectAndReuse" (an alias for "AddRef"), which increments the reference count and is named as such to show the intent that you intend to reuse this node and don't want it to be deleted, and making a new method called "Release" that decrements the reference count and only destroys the node if it falls to zero.  In this case, the code would be "result := ProtectAndReuse;" (it returns Self), then firstpass calls "p.Release;" instead of "p.Free;", since 'result' and 'p' will be identical.

Thanks for warning me about pass 2 though - I think it was just dumb luck that I haven't fallen foul of it yet since I haven't developed anything that caused the nodes to get a reference count of 2 for more than a split second.  The experimentation is mostly for my own benefit, but I like to think I'm getting a better understanding of the compiler as a result and may find and create something useful in the future.

Gareth aka. Kit