![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to PROJECTS CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / cc|
Return to PROJECTS CVS log | Up to [Apple XNU] / GNUtools / cc |
1.1 root 1: 0. Improved efficiency.
2:
3: * Parse and output array initializers an element at a time, freeing
4: storage after each, instead of parsing the whole initializer first and
5: then outputting. This would reduce memory usage for large
6: initializers.
7:
8: * See if the techniques describe in Oct 1991 SIGPLAN Notices
9: (Frazer and Hanson) are applicable to GCC.
10:
11: 1. Better optimization.
12:
13: * Constants in unused inline functions
14:
15: It would be nice to delay output of string constants so that string
16: constants mentioned in unused inline functions are never generated.
17: Perhaps this would also take care of string constants in dead code.
18:
19: The difficulty is in finding a clean way for the RTL which refers
20: to the constant (currently, only by an assembler symbol name)
21: to point to the constant and cause it to be output.
22:
23: * More cse
24:
25: The techniques for doing full global cse are described in the red
26: dragon book, or (a different version) in Frederick Chow's thesis from
27: Stanford. It is likely to be slow and use a lot of memory, but it
28: might be worth offering as an additional option.
29:
30: It is probably possible to extend cse to a few very frequent cases
31: without so much expense.
32:
33: For example, it is not very hard to handle cse through if-then
34: statements with no else clauses. Here's how to do it. On reaching a
35: label, notice that the label's use-count is 1 and that the last
36: preceding jump jumps conditionally to this label. Now you know it
37: is a simple if-then statement. Remove from the hash table
38: all the expressions that were entered since that jump insn
39: and you can continue with cse.
40:
41: It is probably not hard to handle cse from the end of a loop
42: around to the beginning, and a few loops would be greatly sped
43: up by this.
44:
45: * Optimize a sequence of if statements whose conditions are exclusive.
46:
47: It is possible to optimize
48:
49: if (x == 1) ...;
50: if (x == 2) ...;
51: if (x == 3) ...;
52:
53: into
54:
55: if (x == 1) ...;
56: else if (x == 2) ...;
57: else if (x == 3) ...;
58:
59: provided that x is not altered by the contents of the if statements.
60:
61: It's not certain whether this is worth doing. Perhaps programmers
62: nearly always write the else's themselves, leaving few opportunities
63: to improve anything.
64:
65: * Un-cse.
66:
67: Perhaps we should have an un-cse step right after cse, which tries to
68: replace a reg with its value if the value can be substituted for the
69: reg everywhere, if that looks like an improvement. Which is if the
70: reg is used only a few times. Use rtx_cost to determine if the
71: change is really an improvement.
72:
73: * Clean up how cse works.
74:
75: The scheme is that each value has just one hash entry. The
76: first_same_value and next_same_value chains are no longer needed.
77:
78: For arithmetic, each hash table elt has the following slots:
79:
80: * Operation. This is an rtx code.
81: * Mode.
82: * Operands 0, 1 and 2. These point to other hash table elements.
83:
84: So, if we want to enter (PLUS:SI (REG:SI 30) (CONST_INT 104)), we
85: first enter (CONST_INT 104) and find the entry that (REG:SI 30) now
86: points to. Then we put these elts into operands 0 and 1 of a new elt.
87: We put PLUS and SI into the new elt.
88:
89: Registers and mem refs would never be entered into the table as such.
90: However, the values they contain would be entered. There would be a
91: table indexed by regno which points at the hash entry for the value in
92: that reg.
93:
94: The hash entry index now plays the role of a qty number.
95: We still need qty_first_reg, reg_next_eqv, etc. to record which regs
96: share a particular qty.
97:
98: When a reg is used whose contents are unknown, we need to create a
99: hash table entry whose contents say "unknown", as a place holder for
100: whatever the reg contains. If that reg is added to something, then
101: the hash entry for the sum will refer to the "unknown" entry. Use
102: UNKNOWN for the rtx code in this entry. This replaces make_new_qty.
103:
104: For a constant, a unique hash entry would be made based on the
105: value of the constant.
106:
107: What about MEM? Each time a memory address is referenced, we need a
108: qty (a hash table elt) to represent what is in it. (Just as for a
109: register.) If this isn't known, create one, just as for a reg whose
110: contents are unknown.
111:
112: We need a way to find all mem refs that still contain a certain value.
113: Do this with a chain of hash elts (for memory addresses) that point to
114: locations that hold the value. The hash elt for the value itself should
115: point to the start of the chain. It would be good for the hash elt
116: for an address to point to the hash elt for the contents of that address
117: (but this ptr can be null if the contents have never been entered).
118:
119: With this data structure, nothing need ever be invalidated except
120: the lists of which regs or mems hold a particular value. It is easy
121: to see if there is a reg or mem that is equiv to a particular value.
122: If the value is constant, it is always explicitly constant.
123:
124: * Support more general tail-recursion among different functions.
125:
126: This might be possible under certain circumstances, such as when
127: the argument lists of the functions have the same lengths.
128: Perhaps it could be done with a special declaration.
129:
130: You would need to verify in the calling function that it does not
131: use the addresses of any local variables and does not use setjmp.
132:
133: * Put short statics vars at low addresses and use short addressing mode?
134:
135: Useful on the 68000/68020 and perhaps on the 32000 series,
136: provided one has a linker that works with the feature.
137: This is said to make a 15% speedup on the 68000.
138:
139: * Keep global variables in registers.
140:
141: Here is a scheme for doing this. A global variable, or a local variable
142: whose address is taken, can be kept in a register for an entire function
143: if it does not use non-constant memory addresses and (for globals only)
144: does not call other functions. If the entire function does not meet
145: this criterion, a loop may.
146:
147: The VAR_DECL for such a variable would have to have two RTL expressions:
148: the true home in memory, and the pseudo-register used temporarily.
149: It is necessary to emit insns to copy the memory location into the
150: pseudo-register at the beginning of the function or loop, and perhaps
151: back out at the end. These insns should have REG_EQUIV notes so that,
152: if the pseudo-register does not get a hard register, it is spilled into
153: the memory location which exists in any case.
154:
155: The easiest way to set up these insns is to modify the routine
156: put_var_into_stack so that it does not apply to the entire function
157: (sparing any loops which contain nothing dangerous) and to call it at
158: the end of the function regardless of where in the function the
159: address of a local variable is taken. It would be called
160: unconditionally at the end of the function for all relevant global
161: variables.
162:
163: For debugger output, the thing to do is to invent a new binding level
164: around the appropriate loop and define the variable name as a register
165: variable with that scope.
166:
167: * Live-range splitting.
168:
169: Currently a variable is allocated a hard register either for the full
170: extent of its use or not at all. Sometimes it would be good to
171: allocate a variable a hard register for just part of a function; for
172: example, through a particular loop where the variable is mostly used,
173: or outside of a particular loop where the variable is not used. (The
174: latter is nice because it might let the variable be in a register most
175: of the time even though the loop needs all the registers.)
176:
177: It might not be very hard to do this in global.c when a variable
178: fails to get a hard register for its entire life span.
179:
180: The first step is to find a loop in which the variable is live, but
181: which is not the whole life span or nearly so. It's probably best to
182: use a loop in which the variable is heavily used.
183:
184: Then create a new pseudo-register to represent the variable in that loop.
185: Substitute this for the old pseudo-register there, and insert move insns
186: to copy between the two at the loop entry and all exits. (When several
187: such moves are inserted at the same place, some new feature should be
188: added to say that none of those registers conflict merely because of
189: overlap between the new moves. And the reload pass should reorder them
190: so that a store precedes a load, for any given hard register.)
191:
192: After doing this for all the reasonable candidates, run global-alloc
193: over again. With luck, one of the two pseudo-registers will be fit
194: somewhere. It may even have a much higher priority due to its reduced
195: life span.
196:
197: There will be no room in general for the new pseudo-registers in
198: basic_block_live_at_start, so there will need to be a second such
199: matrix exclusively for the new ones. Various other vectors indexed by
200: register number will have to be made bigger, or there will have to be
201: secondary extender vectors just for global-alloc.
202:
203: A simple new feature could arrange that both pseudo-registers get the
204: same stack slot if they both fail to get hard registers.
205:
206: Other compilers split live ranges when they are not connected, or
207: try to split off pieces `at the edge'. I think splitting around loops
208: will provide more speedup.
209:
210: Creating a fake binding block and a new like-named variable with
211: shorter life span and different address might succeed in describing
212: this technique for the debugger.
213:
214: * Detect dead stores into memory?
215:
216: A store into memory is dead if it is followed by another store into
217: the same location; and, in between, there is no reference to anything
218: that might be that location (including no reference to a variable
219: address).
220:
221: * Loop optimization.
222:
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.
229:
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.
233:
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.
238:
239: * Using constraints on values.
240:
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.
248:
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.
254:
255: * Smarter reload pass.
256:
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.
260:
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.
266:
267: * Change the type of a variable.
268:
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.
275:
276: * Better handling for very sparse switches.
277:
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.
281:
282: * Order of subexpressions.
283:
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.
286:
287: * More code motion.
288:
289: Consider hoisting common code up past conditional branches or
290: tablejumps.
291:
292: * Trace scheduling.
293:
294: This technique is said to be able to figure out which way a jump
295: will usually go, and rearrange the code to make that path the
296: faster one.
297:
298: * Distributive law.
299:
300: The C expression *(X + 4 * (Y + C)) compiles better on certain
301: machines if rewritten as *(X + 4*C + 4*Y) because of known addressing
302: modes. It may be tricky to determine when, and for which machines, to
303: use each alternative.
304:
305: Some work has been done on this, in combine.c.
306:
307: * Can optimize by changing if (x) y; else z; into z; if (x) y;
308: if z and x do not interfere and z has no effects not undone by y.
309: This is desirable if z is faster than jumping.
310:
311: * For a two-insn loop on the 68020, such as
312: foo: movb a2@+,a3@+
313: jne foo
314: it is better to insert dbeq d0,foo before the jne.
315: d0 can be a junk register. The challenge is to fit this into
316: a portable framework: when can you detect this situation and
317: still be able to allocate a junk register?
318:
319: 2. Simpler porting.
320:
321: Right now, describing the target machine's instructions is done
322: cleanly, but describing its addressing mode is done with several
323: ad-hoc macro definitions. Porting would be much easier if there were
324: an RTL description for addressing modes like that for instructions.
325: Tools analogous to genflags and genrecog would generate macros from
326: this description.
327:
328: There would be one pattern in the address-description file for each
329: kind of addressing, and this pattern would have:
330:
331: * the RTL expression for the address
332: * C code to verify its validity (since that may depend on
333: the exact data).
334: * C code to print the address in assembler language.
335: * C code to convert the address into a valid one, if it is not valid.
336: (This would replace LEGITIMIZE_ADDRESS).
337: * Register constraints for all indeterminates that appear
338: in the RTL expression.
339:
340: 3. Other languages.
341:
342: Front ends for Pascal, Fortran, Algol, Cobol, Modula-2 and Ada are
343: desirable.
344:
345: Pascal, Modula-2 and Ada require the implementation of functions
346: within functions. Some of the mechanisms for this already exist.
347:
348: 4. More extensions.
349:
350: * Generated unique labels. Have some way of generating distinct labels
351: for use in extended asm statements. I don't know what a good syntax would
352: be.
353:
354: * A way of defining a structure containing a union, in which the choice of
355: union alternative is controlled by a previous structure component.
356:
357: Here is a possible syntax for this.
358:
359: struct foo {
360: enum { INT, DOUBLE } code;
361: auto union { case INT: int i; case DOUBLE: double d;} value : code;
362: };
363:
364: * Allow constructor expressions as lvalues, like this:
365:
366: (struct foo) {a, b, c} = foo();
367:
368: This would call foo, which returns a structure, and then store the
369: several components of the structure into the variables a, b, and c.
370:
371: 5. Generalize the machine model.
372:
373: * Some new compiler features may be needed to do a good job on machines
374: where static data needs to be addressed using base registers.
375:
376: * Some machines have two stacks in different areas of memory, one used
377: for scalars and another for large objects. The compiler does not
378: now have a way to understand this.
379:
380: 6. Useful warnings.
381:
382: * Warn about statements that are undefined because the order of
383: evaluation of increment operators makes a big difference. Here is an
384: example:
385:
386: *foo++ = hack (*foo);
387:
388: 7. Better documentation of how GCC works and how to port it.
389:
390: Here is an outline proposed by Allan Adler.
391:
392: I. Overview of this document
393: II. The machines on which GCC is implemented
394: A. Prose description of those characteristics of target machines and
395: their operating systems which are pertinent to the implementation
396: of GCC.
397: i. target machine characteristics
398: ii. comparison of this system of machine characteristics with
399: other systems of machine specification currently in use
400: B. Tables of the characteristics of the target machines on which
401: GCC is implemented.
402: C. A priori restrictions on the values of characteristics of target
403: machines, with special reference to those parts of the source code
404: which entail those restrictions
405: i. restrictions on individual characteristics
406: ii. restrictions involving relations between various characteristics
407: D. The use of GCC as a cross-compiler
408: i. cross-compilation to existing machines
409: ii. cross-compilation to non-existent machines
410: E. Assumptions which are made regarding the target machine
411: i. assumptions regarding the architecture of the target machine
412: ii. assumptions regarding the operating system of the target machine
413: iii. assumptions regarding software resident on the target machine
414: iv. where in the source code these assumptions are in effect made
415: III. A systematic approach to writing the files tm.h and xm.h
416: A. Macros which require special care or skill
417: B. Examples, with special reference to the underlying reasoning
418: IV. A systematic approach to writing the machine description file md
419: A. Minimal viable sets of insn descriptions
420: B. Examples, with special reference to the underlying reasoning
421: V. Uses of the file aux-output.c
422: VI. Specification of what constitutes correct performance of an
423: implementation of GCC
424: A. The components of GCC
425: B. The itinerary of a C program through GCC
426: C. A system of benchmark programs
427: D. What your RTL and assembler should look like with these benchmarks
428: E. Fine tuning for speed and size of compiled code
429: VII. A systematic procedure for debugging an implementation of GCC
430: A. Use of GDB
431: i. the macros in the file .gdbinit for GCC
432: ii. obstacles to the use of GDB
433: a. functions implemented as macros can't be called in GDB
434: B. Debugging without GDB
435: i. How to turn off the normal operation of GCC and access specific
436: parts of GCC
437: C. Debugging tools
438: D. Debugging the parser
439: i. how machine macros and insn definitions affect the parser
440: E. Debugging the recognizer
441: i. how machine macros and insn definitions affect the recognizer
442:
443: ditto for other components
444:
445: VIII. Data types used by GCC, with special reference to restrictions not
446: specified in the formal definition of the data type
447: IX. References to the literature for the algorithms used in GCC
448:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.