Difference between revisions of "Code Generation Optimization Ideas"

Revision as of 08:49, 7 February 2008

Various ideas about potential improvements to code generation. Once an idea is implemented and is showing a real improvement it should be removed from this page and a new page should describe the mechanism in details with the available results.

Reducing GC hooks

Code generation should only rely on GC hooks when really needed. For example, currently the code:

f (s: STRING)
	local
		i: INTEGER
	do
		i := s.count
		g (s, i)
	end

would generate a hook for the Current object and s, but has the flow shows there is no need for it.

A more complicated case is the following one:

f (s: STRING)
	local
		i: INTEGER
	do
		i := s.count
		h (s, i)
		g (s, i)
	end

If the call to h is guaranteed to not generate any new objects, then it should be safe to not generate the hooks.

Speeding up arrays/strings

One of the issue with ARRAY and STRING is that they are resizable and thus causes an indirection to access the memory area holding the values. In addition, ARRAY have a lower index (an attribute) and STRING a constant lower index of 1.

Getting rid of `lower' in ARRAY

So when you have array.item (i) it is actually array.area.item (i - array.lower). As you can see it is two attribute access via ARRAY. So the idea is to get rid of this by having an additional hidden field in ARRAY called `area0'. This field contains the address of `area' minus or plus the offset to `lower'. With this in mind, the above array access is just array.area0.item (i).

This means that ARRAY and descendants have to be known by the GC so that when the area of the array is changed, the address of `area0' is changed to.

Removing the `area' access altogether

When accessing an of a STRING or ARRAY, we still need to access `area0'. If the object is used as a local, we could also the object along with its `area0'. That is to say the following code:

local
	a: ARRAY [INTEGER]
do
	...
	i := a.item (j)
	...
end

would simply be translated in pseudo C:

local
	area: SPECIAL [INTEGER]
do
	area := a.area0
	...
	i := area.item (j)
	...
end

Thus it is the same speed as today if instead of using an ARRAY you were using a SPECIAL object.

The tricky part of those optimizations are when resizing the ARRAY or STRING. It has to be done via some built-in routine which it is not currently.

Simplifying the stack management

Currently all the hooks are generated one by one for the Current objects, the arguments, and the locals. The idea is to put all of those in one array/structure allocated on the stack. Then only one GC hook will be generated per routine needing the hooks. The other benefit is that because we allocate only one item at the time, we can simplify the code for handling this stack.

Drawback is that each argument and the Current object needs to be copied on routine entry. So for the Eiffel code:

f (s: STRING)
	local
		i: INTEGER
		l_s: STRING
	do
		i := s.count
		l_s := s.twin
		h (s, i)
		g (s, i)
	end

It looks like:

void f (EIF_REFERENCE Current, EIF_REFERENCE s) {
	EIF_INTEGER i;
	EIF_REFERENCE locs [3];
	locs [0] = Current;
	locs [1] = s;
	locs [2] = NULL;
	protect (locs, 3);
 
	i = locs [1].count;
	locs [2] = ANY_twin (locs [1]);
	h (locs [0], locs [1], i);
	g (locs [0], locs [1], i);
}

A solution to this is that all reference arguments are done via the locs array. Which would look like:

void f (EIF_REFERENCE args [2]) {
	EIF_INTEGER i;
	EIF_REFERENCE locs [3];
	locs  [0] = NULL;
	locs  [1] = NULL;
	locs  [2] = NULL;
	protect (locs , 3);
 
	i = args [1].count;
	locs [0] = ANY_twin (args [1]);
	locs [1] = args [0];
	locs [2] = args [1];
	h (&locs [1], i);
	g (&locs [1], i);
}

That is to say that part of the allocated array on the stack is used for the argument passing. The above could even be simplified to just:

void f (EIF_REFERENCE args [2]) {
	EIF_INTEGER i;
	EIF_REFERENCE locs [1];
	locs  [0] = NULL;
	protect (locs, 1);
 
	i = args [1].count;
	locs [0] = ANY_twin (args [1]);
	h (args, i);
	g (args, i);
}