1 C++ template friend functions (mmitchell@usa.net)
3 Haifa scheduler (haifa-sched.c, loop.[ch], unroll.[ch], genattrtab.c):
4 (contact law@cygnus.com before starting any serious haifa work)
6 * Fix all the formatting problems. Simple, mindless work.
8 * Fix/add comments throughout the code. Many of the comments are from
9 the old scheduler and are out of date and misleading. Many new hunks
10 of code don't have sufficient comments and documentation. Those which
11 do have comments need to be rewritten to use complete sentences and
14 * Someone needs make one (or more) passes over the scheduler as a whole to
15 just clean it up. Try to move the machine dependent bits into the target
16 files where they belong, avoid re-creating functions where or near
17 equivalents already exist (ie is_conditional_branch and friends), etc., etc.
19 * Document the new scheduling options. Remove those options which are
20 not really useful (like reverse scheduling for example). In general
21 the haifa scheduler adds _way_ too many options. I'm definitely of the
22 opinion that gcc already has too many -foptions, and haifa doesn't help
25 * Testing and benchmarking. We've converted a few ports to using the
26 Haifa scheduler (hppa, sparc, ppc, alpha). We need to continue testing
27 and benchmarking the new scheduler on additional targets.
29 We need to have some kind of docs for how to best describe a machine to
30 the haifa scheduler to get good performance. Some existing ports have
31 been tuned to deal with the old scheduler -- they may need to be tuned
32 to generate good schedules with haifa.
36 Improvements to global cse and partial redundancy elimination:
38 The current implementation of global cse uses partial redundancy elimination
39 as described in Chow's thesis.
41 Long term we want to use lazy code motion as the basis for partial redundancy
42 elimination. lcm will find as many (or more) redunancies *and* it will
43 place the remaining computations at computationally optimal placement points
44 within the function. This reduces the number of redundant operations performed
45 as well as reducing register lifetimes. My experiments have shown that the
46 cases were the current PRE code hurts performance are greatly helped by using
49 lcm also provides the underlying framework for several additional optimizations
50 such as shrink wrapping, spill code motion, dead store elimination, and generic
51 load/store motion (all the other examples are subcases of load/store motion).
53 It can probably also be used to improve the reg-stack pass of the compiler.
55 Contact law@cygnus.com if you're interested in working on lazy code motion.
59 The old PROJECTS file. Stuff I know has been done has been deleted.
60 Stuff in progress has a contact name associated with it.
63 1. Better optimization.
65 * Constants in unused inline functions
67 It would be nice to delay output of string constants so that string
68 constants mentioned in unused inline functions are never generated.
69 Perhaps this would also take care of string constants in dead code.
71 The difficulty is in finding a clean way for the RTL which refers
72 to the constant (currently, only by an assembler symbol name)
73 to point to the constant and cause it to be output.
75 * Optimize a sequence of if statements whose conditions are exclusive.
77 It is possible to optimize
89 provided that x is not altered by the contents of the if statements.
91 It's not certain whether this is worth doing. Perhaps programmers
92 nearly always write the else's themselves, leaving few opportunities
97 Perhaps we should have an un-cse step right after cse, which tries to
98 replace a reg with its value if the value can be substituted for the
99 reg everywhere, if that looks like an improvement. Which is if the
100 reg is used only a few times. Use rtx_cost to determine if the
101 change is really an improvement.
103 * Clean up how cse works.
105 The scheme is that each value has just one hash entry. The
106 first_same_value and next_same_value chains are no longer needed.
108 For arithmetic, each hash table elt has the following slots:
110 * Operation. This is an rtx code.
112 * Operands 0, 1 and 2. These point to other hash table elements.
114 So, if we want to enter (PLUS:SI (REG:SI 30) (CONST_INT 104)), we
115 first enter (CONST_INT 104) and find the entry that (REG:SI 30) now
116 points to. Then we put these elts into operands 0 and 1 of a new elt.
117 We put PLUS and SI into the new elt.
119 Registers and mem refs would never be entered into the table as such.
120 However, the values they contain would be entered. There would be a
121 table indexed by regno which points at the hash entry for the value in
124 The hash entry index now plays the role of a qty number.
125 We still need qty_first_reg, reg_next_eqv, etc. to record which regs
126 share a particular qty.
128 When a reg is used whose contents are unknown, we need to create a
129 hash table entry whose contents say "unknown", as a place holder for
130 whatever the reg contains. If that reg is added to something, then
131 the hash entry for the sum will refer to the "unknown" entry. Use
132 UNKNOWN for the rtx code in this entry. This replaces make_new_qty.
134 For a constant, a unique hash entry would be made based on the
135 value of the constant.
137 What about MEM? Each time a memory address is referenced, we need a
138 qty (a hash table elt) to represent what is in it. (Just as for a
139 register.) If this isn't known, create one, just as for a reg whose
140 contents are unknown.
142 We need a way to find all mem refs that still contain a certain value.
143 Do this with a chain of hash elts (for memory addresses) that point to
144 locations that hold the value. The hash elt for the value itself should
145 point to the start of the chain. It would be good for the hash elt
146 for an address to point to the hash elt for the contents of that address
147 (but this ptr can be null if the contents have never been entered).
149 With this data structure, nothing need ever be invalidated except
150 the lists of which regs or mems hold a particular value. It is easy
151 to see if there is a reg or mem that is equiv to a particular value.
152 If the value is constant, it is always explicitly constant.
154 * Support more general tail-recursion among different functions.
156 This might be possible under certain circumstances, such as when
157 the argument lists of the functions have the same lengths.
158 Perhaps it could be done with a special declaration.
160 You would need to verify in the calling function that it does not
161 use the addresses of any local variables and does not use setjmp.
163 * Put short statics vars at low addresses and use short addressing mode?
165 Useful on the 68000/68020 and perhaps on the 32000 series,
166 provided one has a linker that works with the feature.
167 This is said to make a 15% speedup on the 68000.
169 * Keep global variables in registers.
171 Here is a scheme for doing this. A global variable, or a local variable
172 whose address is taken, can be kept in a register for an entire function
173 if it does not use non-constant memory addresses and (for globals only)
174 does not call other functions. If the entire function does not meet
175 this criterion, a loop may.
177 The VAR_DECL for such a variable would have to have two RTL expressions:
178 the true home in memory, and the pseudo-register used temporarily.
179 It is necessary to emit insns to copy the memory location into the
180 pseudo-register at the beginning of the function or loop, and perhaps
181 back out at the end. These insns should have REG_EQUIV notes so that,
182 if the pseudo-register does not get a hard register, it is spilled into
183 the memory location which exists in any case.
185 The easiest way to set up these insns is to modify the routine
186 put_var_into_stack so that it does not apply to the entire function
187 (sparing any loops which contain nothing dangerous) and to call it at
188 the end of the function regardless of where in the function the
189 address of a local variable is taken. It would be called
190 unconditionally at the end of the function for all relevant global
193 For debugger output, the thing to do is to invent a new binding level
194 around the appropriate loop and define the variable name as a register
195 variable with that scope.
197 * Live-range splitting.
199 Currently a variable is allocated a hard register either for the full
200 extent of its use or not at all. Sometimes it would be good to
201 allocate a variable a hard register for just part of a function; for
202 example, through a particular loop where the variable is mostly used,
203 or outside of a particular loop where the variable is not used. (The
204 latter is nice because it might let the variable be in a register most
205 of the time even though the loop needs all the registers.)
207 Contact meissner@cygnus.com before starting any work on live range
210 * Detect dead stores into memory?
212 A store into memory is dead if it is followed by another store into
213 the same location; and, in between, there is no reference to anything
214 that might be that location (including no reference to a variable
217 This can be modeled as a partial redundancy elimination/lazy code motion
218 problem. Contact law@cygnus.com before working on dead store elimination
223 Strength reduction and iteration variable elimination could be
224 smarter. They should know how to decide which iteration variables are
225 not worth making explicit because they can be computed as part of an
226 address calculation. Based on this information, they should decide
227 when it is desirable to eliminate one iteration variable and create
228 another in its place.
230 It should be possible to compute what the value of an iteration
231 variable will be at the end of the loop, and eliminate the variable
232 within the loop by computing that value at the loop end.
234 When a loop has a simple increment that adds 1,
235 instead of jumping in after the increment,
236 decrement the loop count and jump to the increment.
237 This allows aob insns to be used.
239 * Using constraints on values.
241 Many operations could be simplified based on knowledge of the
242 minimum and maximum possible values of a register at any particular time.
243 These limits could come from the data types in the tree, via rtl generation,
244 or they can be deduced from operations that are performed. For example,
245 the result of an `and' operation one of whose operands is 7 must be in
246 the range 0 to 7. Compare instructions also tell something about the
247 possible values of the operand, in the code beyond the test.
249 Value constraints can be used to determine the results of a further
250 comparison. They can also indicate that certain `and' operations are
251 redundant. Constraints might permit a decrement and branch
252 instruction that checks zeroness to be used when the user has
253 specified to exit if negative.
255 * Smarter reload pass.
257 The reload pass as currently written can reload values only into registers
258 that are reserved for reloading. This means that in order to use a
259 register for reloading it must spill everything out of that register.
261 It would be straightforward, though complicated, for reload1.c to keep
262 track, during its scan, of which hard registers were available at each
263 point in the function, and use for reloading even registers that were
264 free only at the point they were needed. This would avoid much spilling
265 and make better code.
267 * Change the type of a variable.
269 Sometimes a variable is declared as `int', it is assigned only once
270 from a value of type `char', and then it is used only by comparison
271 against constants. On many machines, better code would result if
272 the variable had type `char'. If the compiler could detect this
273 case, it could change the declaration of the variable and change
274 all the places that use it.
276 * Better handling for very sparse switches.
278 There may be cases where it would be better to compile a switch
279 statement to use a fixed hash table rather than the current
280 combination of jump tables and binary search.
282 * Order of subexpressions.
284 It might be possible to make better code by paying attention
285 to the order in which to generate code for subexpressions of an expression.
289 Consider hoisting common code up past conditional branches or tablejumps.
291 Contact law@cygnus.com before working on code hoisting.
295 This technique is said to be able to figure out which way a jump
296 will usually go, and rearrange the code to make that path the
301 The C expression *(X + 4 * (Y + C)) compiles better on certain
302 machines if rewritten as *(X + 4*C + 4*Y) because of known addressing
303 modes. It may be tricky to determine when, and for which machines, to
304 use each alternative.
306 Some work has been done on this, in combine.c.
308 * Can optimize by changing if (x) y; else z; into z; if (x) y;
309 if z and x do not interfere and z has no effects not undone by y.
310 This is desirable if z is faster than jumping.
312 * For a two-insn loop on the 68020, such as
315 it is better to insert dbeq d0,foo before the jne.
316 d0 can be a junk register. The challenge is to fit this into
317 a portable framework: when can you detect this situation and
318 still be able to allocate a junk register?
322 Right now, describing the target machine's instructions is done
323 cleanly, but describing its addressing mode is done with several
324 ad-hoc macro definitions. Porting would be much easier if there were
325 an RTL description for addressing modes like that for instructions.
326 Tools analogous to genflags and genrecog would generate macros from
329 There would be one pattern in the address-description file for each
330 kind of addressing, and this pattern would have:
332 * the RTL expression for the address
333 * C code to verify its validity (since that may depend on
335 * C code to print the address in assembler language.
336 * C code to convert the address into a valid one, if it is not valid.
337 (This would replace LEGITIMIZE_ADDRESS).
338 * Register constraints for all indeterminates that appear
339 in the RTL expression.
343 Front ends for Pascal, Fortran, Algol, Cobol, Modula-2 and Ada are
346 Pascal, Modula-2 and Ada require the implementation of functions
347 within functions. Some of the mechanisms for this already exist.
351 * Generated unique labels. Have some way of generating distinct labels
352 for use in extended asm statements. I don't know what a good syntax would
355 * A way of defining a structure containing a union, in which the choice of
356 union alternative is controlled by a previous structure component.
358 Here is a possible syntax for this.
361 enum { INT, DOUBLE } code;
362 auto union { case INT: int i; case DOUBLE: double d;} value : code;
365 * Allow constructor expressions as lvalues, like this:
367 (struct foo) {a, b, c} = foo();
369 This would call foo, which returns a structure, and then store the
370 several components of the structure into the variables a, b, and c.
372 5. Generalize the machine model.
374 * Some new compiler features may be needed to do a good job on machines
375 where static data needs to be addressed using base registers.
377 * Some machines have two stacks in different areas of memory, one used
378 for scalars and another for large objects. The compiler does not
379 now have a way to understand this.
383 * Warn about statements that are undefined because the order of
384 evaluation of increment operators makes a big difference. Here is an
387 *foo++ = hack (*foo);
389 7. Better documentation of how GCC works and how to port it.
391 Here is an outline proposed by Allan Adler.
393 I. Overview of this document
394 II. The machines on which GCC is implemented
395 A. Prose description of those characteristics of target machines and
396 their operating systems which are pertinent to the implementation
398 i. target machine characteristics
399 ii. comparison of this system of machine characteristics with
400 other systems of machine specification currently in use
401 B. Tables of the characteristics of the target machines on which
403 C. A priori restrictions on the values of characteristics of target
404 machines, with special reference to those parts of the source code
405 which entail those restrictions
406 i. restrictions on individual characteristics
407 ii. restrictions involving relations between various characteristics
408 D. The use of GCC as a cross-compiler
409 i. cross-compilation to existing machines
410 ii. cross-compilation to non-existent machines
411 E. Assumptions which are made regarding the target machine
412 i. assumptions regarding the architecture of the target machine
413 ii. assumptions regarding the operating system of the target machine
414 iii. assumptions regarding software resident on the target machine
415 iv. where in the source code these assumptions are in effect made
416 III. A systematic approach to writing the files tm.h and xm.h
417 A. Macros which require special care or skill
418 B. Examples, with special reference to the underlying reasoning
419 IV. A systematic approach to writing the machine description file md
420 A. Minimal viable sets of insn descriptions
421 B. Examples, with special reference to the underlying reasoning
422 V. Uses of the file aux-output.c
423 VI. Specification of what constitutes correct performance of an
424 implementation of GCC
425 A. The components of GCC
426 B. The itinerary of a C program through GCC
427 C. A system of benchmark programs
428 D. What your RTL and assembler should look like with these benchmarks
429 E. Fine tuning for speed and size of compiled code
430 VII. A systematic procedure for debugging an implementation of GCC
432 i. the macros in the file .gdbinit for GCC
433 ii. obstacles to the use of GDB
434 a. functions implemented as macros can't be called in GDB
435 B. Debugging without GDB
436 i. How to turn off the normal operation of GCC and access specific
439 D. Debugging the parser
440 i. how machine macros and insn definitions affect the parser
441 E. Debugging the recognizer
442 i. how machine macros and insn definitions affect the recognizer
444 ditto for other components
446 VIII. Data types used by GCC, with special reference to restrictions not
447 specified in the formal definition of the data type
448 IX. References to the literature for the algorithms used in GCC