Whole Program Optimization: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: Whole Program Optimization

New		Line
1	+	## Overview
2	+
3	+	Traditionally, compilers optimize a program procedure by procedure, or at best compilation unit per compilation unit. Whole program optimization, abbreviated WPO, means that the compiler considers all compilation units that make up a program or library and optimizes them using the comprehensive knowledge of how they are used together in this particular case.
4	+
5	+	The way WPO generally works is as follows:
6	+
7	+	- you compile the program normally, telling the compiler to store various bits of information into a feedback file
8	+	- you recompile the program (and optionally all units that it uses) with WPO, providing the feedback file as extra input to the compiler
9	+
10	+	In some implementations, the compiler generates some kind of intermediary code (e.g., byte code) and the linker performs all WPO along with the translation to the target ISA. In case of FPC however, the scheme followed is the one described above.
11	+
12	+	## General principles
13	+
14	+	A few general principles have been followed when designing the FPC implementation of WPO:
15	+
16	+	- All information necessary to generate a WPO feedback file for a program is always stored in the PPU files. This means that you can e.g. use a generic RTL for WPO (even though the RTL itself will then not be optimized, your program and its units can be correctly optimized because the compiler knows everything it has to know about all RTL units);
17	+	- The generated WPO feedback file is plain text. The idea is that it should be easy to inspect this file by hand, and to add information to it produced by external tools if desired (e.g., profile information);
18	+	- The implementation of the WPO subsystem in the compiler is very modular, so it should be easy to plug in additional WPO information providers, or to choose at run time between different information providers for the same kind of information. At the same time, the interaction with the rest of the compiler is kept to a bare minimum to improve maintainability;
19	+	- It is possible to generate a WPO feedback file while at the same time using another one as input. In some cases, using this second feedback file as input during a third compilation can further improve the results.
20	+
21	+	## How to use
22	+
23	+	### Generate WPO feedback file
24	+
25	+	First of all, compile your program (or library) and all of its units as you would normally do, except that when compiling the main program/library you add
26	+
27	+	``` bash
28	+	-FW/path/to/feedbackfile.wpo -OW<selected_wpo_options>
29	+	```
30	+
31	+	. The compiler will then, right after your program has been linked, collect all necessary information to perform the requested WPOs during a successive compilation run, and store this information in `/path/to/feedbackfile.wpo`.
32	+
33	+	### Use generated WPO feedback file
34	+
35	+	To actually apply the WPOs, recompile the program/library and all or some of the units that it uses, using
36	+
37	+	``` bash
38	+	-Fw/path/to/feedbackfile.wpo -Ow<selected_wpo_options>
39	+	```
40	+
41	+	, thereby pointing the compiler to the feedback file generated in the previous step. The compiler will then read the information collected about the program during the previous compiler run, and use it during the current compilation of units and/or program/library.
42	+
43	+	Units not recompiled during the second pass will obviously not be optimized, but they will still work correctly when used together with the optimized units and program/library.
44	+
45	+	### Concrete example
46	+
47	+	The example below refers to [`twpo4.pp`](https://gitlab.com/freepascal.org/fpc/source/-/blob/main/tests/test/opt/twpo4.pp).
48	+
49	+	Compile the program a first time, collecting feedback in `twpo4-1.wpo` in the current directory. The compiler will record which classes are created in the program (`tchild1` and `tchild2`), and after the linking step also that the `notcalled` procedure is in fact not called.
50	+
51	+	Afterwards, save the generated assembler code in `twpo4.s1` for later comparison.
52	+
53	+	$ ppn37 -FWtwpo4-1.wpo -OWall -CX -XX -Xs- -al twpo4
54	+	Free Pascal Compiler version 2.3.1 [2008/12/11] for i386
55	+	Copyright (c) 1993-2008 by Florian Klaempfl
56	+	Target OS: Darwin for i386
57	+	Compiling twpo4.pp
58	+	Assembling program
59	+	Linking twpo4
60	+	66 lines compiled, 0.6 sec
61	+	$ mv twpo4.s twpo4.s1
62	+
63	+	Now compile the program a second time, using the information in `twpo4-1.wpo` and collecting new information in `twpo4-2.wpo`. At this point, the compiler knows that no instance of the `tbase` class is created in the program, and therefore it replaces all regular entries in its virtual method table with references to `FPC_ABSTRACTERROR`. Virtual class methods cannot be eliminated this way, since they can also be called without constructing an instance of this type.
64	+
65	+	Because the compiler knows from the previously generated feedback file that the `notcalled` procedure is never called, it will also record that only an instance of `tchild1` is created, as the `tchild2` instance was only created inside this `notcalled` procedure. For optimization purposes, it will however still consider that an instance of `tchild2` may be created, as for optimization purposes it still uses the feedback file generated during the previous compilation.
66	+
67	+	Afterwards, we again save the generated assembler code for later comparisons.
68	+
69	+	$ ppn37 -FWtwpo4-2.wpo -OWall -Fwtwpo4-1.wpo -Owall -CX -XX -Xs- -al twpo4
70	+	Free Pascal Compiler version 2.3.1 [2008/12/11] for i386
71	+	Copyright (c) 1993-2008 by Florian Klaempfl
72	+	Target OS: Darwin for i386
73	+	Compiling twpo4.pp
74	+	Assembling program
75	+	Linking twpo4
76	+	66 lines compiled, 0.1 sec
77	+	$ mv twpo4.s twpo4.s2
78	+
79	+	Compile the program a final time, using the information collected in `twpo4-2.wpo`. This time, the compiler knows that only a `tchild1` instance is created, and will therefore turn the `bb.test` call from a virtual method call into a static method call (because it knows that even though the type of `bb` is `tbase`, in practice it can only be a `tchild1` since no `tbaseh` or other `tbase`-descendent class instance is created).
80	+
81	+	$ ppn37 -Fwtwpo4-2.wpo -Owall -CX -XX -al twpo4
82	+	Free Pascal Compiler version 2.3.1 [2008/12/11] for i386
83	+	Copyright (c) 1993-2008 by Florian Klaempfl
84	+	Target OS: Darwin for i386
85	+	Compiling twpo4.pp
86	+	Assembling program
87	+	Linking twpo4
88	+	66 lines compiled, 0.1 sec
89	+
90	+	Now, let's have a look at the differences between the generated assembler files. After the first recompilation:
91	+
92	+	``` bash
93	+	$ diff -u twpo4.s1 twpo4.s2
94	+	```
95	+
96	+	``` diff
97	+	--- twpo4.s1 2008-12-11 18:59:55.000000000 +0100
98	+	+++ twpo4.s2 2008-12-11 19:00:15.000000000 +0100
99	+	@@ -214,15 +214,15 @@
100	+	.long 0,0,0
101	+	.long FPC_EMPTYINTF
102	+	.long 0
103	+	- .long _SYSTEM_TOBJECT_$__DESTROY
104	+	+ .long FPC_ABSTRACTERROR
105	+	.long _SYSTEM_TOBJECT_$__NEWINSTANCE$$TOBJECT
106	+	- .long _SYSTEM_TOBJECT_$__FREEINSTANCE
107	+	- .long _SYSTEM_TOBJECT_$__SAFECALLEXCEPTION$TOBJECT$POINTER$$LONGINT
108	+	- .long _SYSTEM_TOBJECT_$__DEFAULTHANDLER$formal
109	+	- .long _SYSTEM_TOBJECT_$__AFTERCONSTRUCTION
110	+	- .long _SYSTEM_TOBJECT_$__BEFOREDESTRUCTION
111	+	- .long _SYSTEM_TOBJECT_$__DEFAULTHANDLERSTR$formal
112	+	- .long _P$PROGRAM_TBASE_$__TEST
113	+	+ .long FPC_ABSTRACTERROR
114	+	+ .long FPC_ABSTRACTERROR
115	+	+ .long FPC_ABSTRACTERROR
116	+	+ .long FPC_ABSTRACTERROR
117	+	+ .long FPC_ABSTRACTERROR
118	+	+ .long FPC_ABSTRACTERROR
119	+	+ .long FPC_ABSTRACTERROR
120	+	.long 0
121	+
122	+	.const_data
123	+	```
124	+
125	+	As you can see, all references to the virtual methods in the virtual method table of `tbase` have been removed, since the compiler knows they can never be referenced. This allows the linker to throw away these methods if they are not referenced anywhere else either. In our example, that is only true for `tbase.test`.
126	+
127	+	Now let's look at the effect of the second recompilation:
128	+
129	+	``` bash
130	+	$ diff -u twpo4.s2 twpo4.s
131	+	```
132	+
133	+	``` diff
134	+	--- twpo4.s2 2008-12-11 19:00:15.000000000 +0100
135	+	+++ twpo4.s 2008-12-11 19:00:29.000000000 +0100
136	+	@@ -103,9 +103,7 @@
137	+	movl %eax,-4(%ebp)
138	+	# [54] bb.test;
139	+	movl -4(%ebp),%eax
140	+	- movl -4(%ebp),%edx
141	+	- movl (%edx),%edx
142	+	- call *80(%edx)
143	+	+ call L_P$PROGRAM_TCHILD1_$__TEST$stub
144	+	# [55] bb.free;
145	+	movl -4(%ebp),%eax
146	+	call L_SYSTEM_TOBJECT_$__FREE$stub
147	+	@@ -139,10 +137,7 @@
148	+	# [63] bb.test;
149	+	movl L_U_P$PROGRAM_BB$non_lazy_ptr-Lj2(%ebx),%eax
150	+	movl (%eax),%eax
151	+	- movl L_U_P$PROGRAM_BB$non_lazy_ptr-Lj2(%ebx),%edx
152	+	- movl (%edx),%edx
153	+	- movl (%edx),%edx
154	+	- call *80(%edx)
155	+	+ call L_P$PROGRAM_TCHILD1_$__TEST$stub
156	+	# [64] a:=2;
157	+	movl L_U_P$PROGRAM_A$non_lazy_ptr-Lj2(%ebx),%eax
158	+	movl $2,(%eax)
159	+	```
160	+
161	+	As you can see, the two virtual method calls to bb.test (one inside the never called notcalled procedure, and one in the main program) have been replaced with calls to tchild1.test.
162	+
163	+	Note that you could also recompile the entire run time library for this particular program, if you want.
164	+
165	+	### Concrete Lazarus IDE example
166	+
167	+	To setup Whole Program Optimization in Lazarus IDE, add two new Build Modes for each platform. For example:
168	+
169	+	- "Linux WPO Pass1"
170	+	- "Linux WPO Pass2"
171	+	- "Windows WPO Pass1"
172	+	- "Windows WPO Pass2"
173	+
174	+	![](/wiki-images/9/9d/01_Add_New_Build_Modes.png)
175	+
176	+	See: [[IDE Window: Compiler Options\|IDE Window: Compiler Options#Build modes]].
177	+
178	+	Switch to Build mode "Linux WPO Pass1". Under "Compiler Options \\| Custom Options", add the Custom Options "-OWall -FWtemplinux.wpo -Xs- -CX" (case sensitive, should be UPPERCASE "W").
179	+
180	+	![](/wiki-images/8/8f/02_Linux_WPO_Pass1.png)
181	+
182	+	Switch to Build mode "Linux WPO Pass2". Under "Compiler Options \\| Custom Options", add the Custom Options "-Owall -Fwtemplinux.wpo -Xs- -CX" (case sensitive, should be lowercase "w").
183	+
184	+	![](/wiki-images/5/59/03_Linux_WPO_Pass2.png)
185	+
186	+	Switch to Build mode "Windows WPO Pass1". Under "Compiler Options \\| Custom Options", add the Custom Options "-OWDEVIRTCALLS,OPTVMTS -FWtempwindows.wpo -CX -XX -Xs-" (case sensitive, should be UPPERCASE "W").
187	+
188	+	![](/wiki-images/0/07/04_Windows_WPO_Pass1.png)
189	+
190	+	Switch to Build mode "Windows WPO Pass2". Under "Compiler Options \\| Custom Options", add the Custom Options "-OwDEVIRTCALLS,OPTVMTS -Fwtempwindows.wpo -CX -XX -Xs-" (case sensitive, should be lowercase "w").
191	+
192	+	![](/wiki-images/e/e4/05_Windows_WPO_Pass2.png)
193	+
194	+	When you are happy with your Project Options settings, you might want to click the Export button, to save them to an XML file, which you can import into other projects later.
195	+
196	+	When you are ready to compile your program, from the IDE menu, select "Run \\| Compile Many Modes". Select both Pass1 and Pass2 to compile in exactly that proper order.
197	+
198	+	![](/wiki-images/0/04/06_Build_Many_Modes.png)
199	+
200	+	If your Build Modes are out of sequence, you could simply compile each Pass separately, in proper order. Alternatively, you could very carefully manually edit in a text editor your LPI project file (after first making a backup copy), to put the Passes into correct order.
201	+
202	+	## When to use
203	+
204	+	Since whole program optimization requires multiple compilations, it is advisable to only use this functionality when compiling a final release version.
205	+
206	+	Also keep in mind that once a unit has been compiled using wpo for a particular program, it has to be recompiled if you want to use it in another program.
207	+
208	+	## Available whole program optimizations
209	+
210	+	### All optimizations
211	+
212	+	parameter
213	+
214	+	:
215	+
216	+	``` bash
217	+	-OWall/-Owall
218	+	```
219	+
220	+	effect
221	+	Enables all whole program optimizations described below.
222	+
223	+	limitations
224	+	The combined limitations of all optimizations described below.
225	+
226	+	### Whole program devirtualization
227	+
228	+	parameter
229	+
230	+	:
231	+
232	+	``` bash
233	+	-OWdevirtcalls/-Owdevirtcalls
234	+	```
235	+
236	+	effect
237	+	Changes virtual method calls into normal (static) method calls when the compiler can determine that a virtual method call will always go to the same static method. This makes such code both smaller and faster. In general, it's mainly an enabling optimization for other optimizations, because it makes the program easier to analyse due to the fact that it reduces indirect control flow.
238	+
239	+	limitations
240	+
241	+	- The current implementation is context-insensitive. This means that the compiler only looks at the program as a whole and determines for each class type which methods can be devirtualised, rather than that it looks at each call statement and the surrounding code to determine whether or not this call can be devirtualised;
242	+	- The current implementation does not yet devirtualise interface method calls (not when calling them via an interface instance, nor when calling them via a class instance).
243	+
244	+	### Optimise virtual method tables
245	+
246	+	parameter
247	+
248	+	:
249	+
250	+	``` bash
251	+	-OWoptvmts/-Owoptvmts
252	+	```
253	+
254	+	effect
255	+	This optimization looks at which class types can be instantiated and which virtual methods can be called in a program, and based on this information it replaces virtual method table (VMT) entries that can never be called with references to FPC_ABSTRACTERROR. This means that such methods, unless they are called directly via an inherited call from a child class/object, can be removed by the linker. It has little or no effect on speed, but can help reducing code size.
256	+
257	+	limitations
258	+
259	+	- Methods that are published, or getters/setters of published properties, can never be optimized in this way, because they can always be referred to and called via the RTTI (which the compiler cannot detect).
260	+	- Such optimizations are not yet done for virtual class methods (but it should not be that difficult to add)
261	+
262	+	### Symbol liveness
263	+
264	+	parameter
265	+
266	+	:
267	+
268	+	``` bash
269	+	-OWsymbolliveness/-Owsymbolliveness
270	+	```
271	+
272	+	effect
273	+	This parameter does not perform any optimization by itself. It simply tells the compiler to record which functions/procedures were kept by the linker in the final program. During a subsequent wpo pass, the compiler can then ignore the removed functions/procedures as far as wpo is concerned (e.g., if a particular class type is only constructed in one unused procedure, then ignoring this procedure can improve the effectiveness of the previous two optimizations).
274	+
275	+	limitations
276	+
277	+	- This optimization requires that the `nm(1)` utility is installed on the system. For Linux binaries, `objdump(1)` will also work. In the future, this information could also be extracted from the internal linker for the platforms that it supports.
278	+	- Collecting information for this optimization (using -OWsymbolliveness) requires that smart linking is enabled (-XX) and that symbol stripping is disabled (-Xs-). When only using such previously collected information (using -OwSymbolliveness or -Owall), these limitations do not apply.
279	+
280	+	## Format of the WPO feedback file
281	+
282	+	This information is mainly interesting if you want to add external data to the WPO feedback file, e.g. from a profiling tool. If you are just a user of the WPO functionality, you can ignore what follows.
283	+
284	+	The file consists of comments and a number of sections. Comments are lines that start with a `#`. Each section starts with `%` (percent sign and space) followed by the name of the section (e.g.,`% contextinsensitive_devirtualization`). After that, until either the end of the file or until the next line starting with with "`%`", first a human readable description follows of the format of this section (in comments), and then the contents of the section itself.
285	+
286	+	There are no rules for how the contents of a section should look, except that lines starting with `#` are reserved for comments and lines starting with `%` are reserved for section markers.
287	+
288	+	---
289	+	From the Free Pascal wiki, page "Whole Program Optimization", as it stood on 2022-08-06 after a change by Kai Burghardt, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).
290	+	Category: FPC
291	+	Category: Tutorials

Back to history