Code Generation Optimization Ideas - Revision history

Alexander Kogtenkov: /* Loop specialization */ Cosmetics

2010-04-27T14:41:31Z

‎Loop specialization: Cosmetics

Alexander Kogtenkov: Corrected categories

2010-04-27T14:40:07Z

Corrected categories

Alexander Kogtenkov: Added sections describing loop optimizations

2010-04-27T14:39:06Z

Added sections describing loop optimizations

Alexander Kogtenkov: Added a new category: optimization

2010-04-27T14:18:10Z

Added a new category: optimization

Manus: /* Getting rid of `lower' in ARRAY */

2008-02-07T17:54:20Z

‎Getting rid of `lower' in ARRAY

Manus: /* Removing the `area' access altogether */

2008-02-07T17:53:39Z

‎Removing the `area' access altogether

Manus: /* Simplifying the stack management */

2008-02-07T17:50:45Z

‎Simplifying the stack management

Manus: ARRAY/STRING optimization

2008-02-07T17:49:05Z

ARRAY/STRING optimization

Manus: /* Simplifying the stack management */

2008-01-29T17:20:19Z

‎Simplifying the stack management

Manus at 21:22, 28 January 2008

2008-01-28T21:22:24Z

← Older revision		Revision as of 14:41, 27 April 2010
Line 154:		Line 154:
	before the loop we can compute the type of <e>a</e> and then generate 3 different loops: one if the dynamic type is <e>ARRAY</e>, one if the dynamic type is <e>ARRAYED_LIST</e> and one if the dynamic type is anything else. In that case access to items of <e>ARRAY</e> and <e>ARRAYED_LIST</e> is performed at full speed without any dynamic feature calls, yet it also works for descendants, making the code flexible.		before the loop we can compute the type of <e>a</e> and then generate 3 different loops: one if the dynamic type is <e>ARRAY</e>, one if the dynamic type is <e>ARRAYED_LIST</e> and one if the dynamic type is anything else. In that case access to items of <e>ARRAY</e> and <e>ARRAYED_LIST</e> is performed at full speed without any dynamic feature calls, yet it also works for descendants, making the code flexible.

−	This optimization becomes even more important for iterator-based form of a loop as there are usually several feature calls for every iteration. Such feature calls can be inlined and become subject to [[#Invariant code motion]].	+	This optimization becomes even more important for iterator-based form of a loop as there are usually several feature calls for every iteration. Such feature calls can be inlined and become subject to [[#Invariant code motion\|Invariant code motion]].

← Older revision		Revision as of 14:40, 27 April 2010
Line 1:		Line 1:
−	[[Category:Code Generation, Optimization]]	+	[[Category:Code Generation]]
		+	[[Category:Optimization]]
	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.		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.

← Older revision		Revision as of 14:39, 27 April 2010
Line 131:		Line 131:
	}		}
	</c>		</c>
		+
		+	==Invariant code motion==
		+	This technique is widely used in production compilers to move invariant parts of code outside of the loops. Since important high-level information about Eiffel code is lost during code generation it makes sense to perform this kind of optimization at code generation time. Presence of the moving GC and dynamic nature of objects makes it difficult to track computations that may be performed before or after the loop without affecting the results, but the clear candidates for that are:
		+	* types of read-only entities
		+	* addresses of features of read-only entities
		+	* offsets of attributes of read-only entities
		+	They can be computed before the loop and used afterwards without the need to recompute them at every iteration.
		+
		+	==Loop specialization==
		+	As soon as a loop is applied to a specific data structure the corresponding dynamic feature calls can be replaced by static ones. For example, if we have a loop
		+	<e>
		+	from
		+	i := 1
		+	until
		+	i > a.count
		+	loop
		+	do_something_with (a [i])
		+	i := i + 1
		+	end
		+	</e>
		+	before the loop we can compute the type of <e>a</e> and then generate 3 different loops: one if the dynamic type is <e>ARRAY</e>, one if the dynamic type is <e>ARRAYED_LIST</e> and one if the dynamic type is anything else. In that case access to items of <e>ARRAY</e> and <e>ARRAYED_LIST</e> is performed at full speed without any dynamic feature calls, yet it also works for descendants, making the code flexible.
		+
		+	This optimization becomes even more important for iterator-based form of a loop as there are usually several feature calls for every iteration. Such feature calls can be inlined and become subject to [[#Invariant code motion]].

← Older revision		Revision as of 14:18, 27 April 2010
Line 1:		Line 1:
−	[[Category:Code Generation]]	+	[[Category:Code Generation, Optimization]]
	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.		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.

@@ Line 33: / Line 33: @@
 So when you have <e>array.item (i)</e> it is actually <e>array.area.item (i - array.lower)</e>. 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 <e>array.area0.item (i)</e>.
-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.
+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 also changed to its new value.
 ===Removing the `area' access altogether===

@@ Line 36: / Line 36: @@
 ===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:
+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 record the object along with its `area0'. That is to say the following code:
 <e>
@@ Line 51: / Line 51: @@
 <e>
 local
 	area: SPECIAL [INTEGER]
 do
@@ Line 62: / Line 63: @@
 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.
+===Tricky part===
 ==Simplifying the stack management==

@@ Line 115: / Line 115: @@
+}
 </c>
-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:
+That is to say the last part of the allocated array on the stack is used for the argument passing. The above could even be simplified to just:
 <c>
 void f (EIF_REFERENCE args [2]) {

@@ Line 26: / Line 26: @@
 </e>
 If the call to <e>h</e> is guaranteed to not generate any new objects, then it should be safe to not generate the hooks.
 ==Simplifying the stack management==

@@ Line 51: / Line 51: @@
 	locs [1] = s;
 	locs [2] = NULL;
-	protect (locs );
+	protect (locs, 3);
 	i = locs [1].count;
@@ Line 68: / Line 68: @@
 	locs  [1] = NULL;
 	locs  [2] = NULL;
-	protect (locs );
+	protect (locs , 3);
 	i = args [1].count;
@@ Line 84: / Line 84: @@
 	EIF_REFERENCE locs [1];
 	locs  [0] = NULL;
-	protect (locs );
+	protect (locs, 1);
 	i = args [1].count;

@@ Line 53: / Line 53: @@
 	protect (locs );
-	i := locs [1].count;
+	i = locs [1].count;
 	locs [2] = ANY_twin (locs [1]);
 	h (locs [0], locs [1], i);
@@ Line 70: / Line 70: @@
 	protect (locs );
-	i := args [1].count;
+	i = args [1].count;
 	locs [0] = ANY_twin (args [1]);
 	locs [1] = args [0];
@@ Line 86: / Line 86: @@
 	protect (locs );
-	i := args [1].count;
+	i = args [1].count;
 	locs [0] = ANY_twin (args [1]);
 	h (args, i);