Return to PROJECTS CVS log

Up to [GCC 2.x] / gcc

Annotation of gcc/PROJECTS, revision 1.1

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: * Support more general tail-recursion among different functions.
        !            74: 
        !            75: This might be possible under certain circumstances, such as when
        !            76: the argument lists of the functions have the same lengths.
        !            77: Perhaps it could be done with a special declaration.
        !            78: 
        !            79: You would need to verify in the calling function that it does not
        !            80: use the addresses of any local variables and does not use setjmp.
        !            81: 
        !            82: * Put short statics vars at low addresses and use short addressing mode?
        !            83: 
        !            84: Useful on the 68000/68020 and perhaps on the 32000 series,
        !            85: provided one has a linker that works with the feature.
        !            86: This is said to make a 15% speedup on the 68000.
        !            87: 
        !            88: * Keep global variables in registers.
        !            89: 
        !            90: Here is a scheme for doing this.  A global variable, or a local variable
        !            91: whose address is taken, can be kept in a register for an entire function
        !            92: if it does not use non-constant memory addresses and (for globals only)
        !            93: does not call other functions.  If the entire function does not meet
        !            94: this criterion, a loop may.
        !            95: 
        !            96: The VAR_DECL for such a variable would have to have two RTL expressions:
        !            97: the true home in memory, and the pseudo-register used temporarily. 
        !            98: It is necessary to emit insns to copy the memory location into the
        !            99: pseudo-register at the beginning of the function or loop, and perhaps
        !           100: back out at the end.  These insns should have REG_EQUIV notes so that,
        !           101: if the pseudo-register does not get a hard register, it is spilled into
        !           102: the memory location which exists in any case.
        !           103: 
        !           104: The easiest way to set up these insns is to modify the routine
        !           105: put_var_into_stack so that it does not apply to the entire function
        !           106: (sparing any loops which contain nothing dangerous) and to call it at
        !           107: the end of the function regardless of where in the function the
        !           108: address of a local variable is taken.  It would be called
        !           109: unconditionally at the end of the function for all relevant global
        !           110: variables.
        !           111: 
        !           112: For debugger output, the thing to do is to invent a new binding level
        !           113: around the appropriate loop and define the variable name as a register
        !           114: variable with that scope.
        !           115: 
        !           116: * Live-range splitting.
        !           117: 
        !           118: Currently a variable is allocated a hard register either for the full
        !           119: extent of its use or not at all.  Sometimes it would be good to
        !           120: allocate a variable a hard register for just part of a function; for
        !           121: example, through a particular loop where the variable is mostly used,
        !           122: or outside of a particular loop where the variable is not used.  (The
        !           123: latter is nice because it might let the variable be in a register most
        !           124: of the time even though the loop needs all the registers.)
        !           125: 
        !           126: It might not be very hard to do this in global-alloc.c when a variable
        !           127: fails to get a hard register for its entire life span.
        !           128: 
        !           129: The first step is to find a loop in which the variable is live, but
        !           130: which is not the whole life span or nearly so.  It's probably best to
        !           131: use a loop in which the variable is heavily used.
        !           132: 
        !           133: Then create a new pseudo-register to represent the variable in that loop.
        !           134: Substitute this for the old pseudo-register there, and insert move insns
        !           135: to copy between the two at the loop entry and all exits.  (When several
        !           136: such moves are inserted at the same place, some new feature should be
        !           137: added to say that none of those registers conflict merely because of
        !           138: overlap between the new moves.  And the reload pass should reorder them
        !           139: so that a store precedes a load, for any given hard register.)
        !           140: 
        !           141: After doing this for all the reasonable candidates, run global-alloc
        !           142: over again.  With luck, one of the two pseudo-registers will be fit
        !           143: somewhere.  It may even have a much higher priority due to its reduced
        !           144: life span.
        !           145: 
        !           146: There will be no room in general for the new pseudo-registers in
        !           147: basic_block_live_at_start, so there will need to be a second such
        !           148: matrix exclusively for the new ones.  Various other vectors indexed by
        !           149: register number will have to be made bigger, or there will have to be
        !           150: secondary extender vectors just for global-alloc.
        !           151: 
        !           152: A simple new feature could arrange that both pseudo-registers get the
        !           153: same stack slot if they both fail to get hard registers.
        !           154: 
        !           155: Other compilers split live ranges when they are not connected, or
        !           156: try to split off pieces `at the edge'.  I think splitting around loops
        !           157: will provide more speedup.
        !           158: 
        !           159: Creating a fake binding block and a new like-named variable with
        !           160: shorter life span and different address might succeed in describing
        !           161: this technique for the debugger.
        !           162: 
        !           163: * Detect dead stores into memory?
        !           164: 
        !           165: A store into memory is dead if it is followed by another store into
        !           166: the same location; and, in between, there is no reference to anything
        !           167: that might be that location (including no reference to a variable
        !           168: address).
        !           169: 
        !           170: * Loop optimization.
        !           171: 
        !           172: Strength reduction and iteration variable elimination could be
        !           173: smarter.  They should know how to decide which iteration variables are
        !           174: not worth making explicit because they can be computed as part of an
        !           175: address calculation.  Based on this information, they should decide
        !           176: when it is desirable to eliminate one iteration variable and create
        !           177: another in its place.
        !           178: 
        !           179: It should be possible to compute what the value of an iteration
        !           180: variable will be at the end of the loop, and eliminate the variable
        !           181: within the loop by computing that value at the loop end.
        !           182: 
        !           183: When a loop has a simple increment that adds 1,
        !           184: instead of jumping in after the increment,
        !           185: decrement the loop count and jump to the increment.
        !           186: This allows aob insns to be used.
        !           187: 
        !           188: * Using constraints on values.
        !           189: 
        !           190: Many operations could be simplified based on knowledge of the
        !           191: minimum and maximum possible values of a register at any particular time.
        !           192: These limits could come from the data types in the tree, via rtl generation,
        !           193: or they can be deduced from operations that are performed.  For example,
        !           194: the result of an `and' operation one of whose operands is 7 must be in
        !           195: the range 0 to 7.  Compare instructions also tell something about the
        !           196: possible values of the operand, in the code beyond the test.
        !           197: 
        !           198: Value constraints can be used to determine the results of a further
        !           199: comparison.  They can also indicate that certain `and' operations are
        !           200: redundant.  Constraints might permit a decrement and branch
        !           201: instruction that checks zeroness to be used when the user has
        !           202: specified to exit if negative.
        !           203: 
        !           204: * Smarter reload pass.
        !           205: 
        !           206: The reload pass as currently written can reload values only into registers
        !           207: that are reserved for reloading.  This means that in order to use a
        !           208: register for reloading it must spill everything out of that register.
        !           209: 
        !           210: It would be straightforward, though complicated, for reload1.c to keep
        !           211: track, during its scan, of which hard registers were available at each
        !           212: point in the function, and use for reloading even registers that were
        !           213: free only at the point they were needed.  This would avoid much spilling
        !           214: and make better code.
        !           215: 
        !           216: * Change the type of a variable.
        !           217: 
        !           218: Sometimes a variable is declared as `int', it is assigned only once
        !           219: from a value of type `char', and then it is used only by comparison
        !           220: against constants.  On many machines, better code would result if
        !           221: the variable had type `char'.  If the compiler could detect this
        !           222: case, it could change the declaration of the variable and change
        !           223: all the places that use it.
        !           224: 
        !           225: * Better handling for very sparse switches.
        !           226: 
        !           227: There may be cases where it would be better to compile a switch
        !           228: statement to use a fixed hash table rather than the current
        !           229: combination of jump tables and binary search.
        !           230: 
        !           231: * Order of subexpressions.
        !           232: 
        !           233: It might be possible to make better code by paying attention
        !           234: to the order in which to generate code for subexpressions of an expression.
        !           235: 
        !           236: * More code motion.
        !           237: 
        !           238: Consider hoisting common code up past conditional branches or
        !           239: tablejumps.
        !           240: 
        !           241: * Trace scheduling.
        !           242: 
        !           243: This technique is said to be able to figure out which way a jump
        !           244: will usually go, and rearrange the code to make that path the
        !           245: faster one.
        !           246: 
        !           247: * Distributive law.
        !           248: 
        !           249: The C expression *(X + 4 * (Y + C)) compiles better on certain
        !           250: machines if rewritten as *(X + 4*C + 4*Y) because of known addressing
        !           251: modes.  It may be tricky to determine when, and for which machines, to
        !           252: use each alternative.
        !           253: 
        !           254: Some work has been done on this, in combine.c.
        !           255: 
        !           256: * Can optimize by changing if (x) y; else z; into z; if (x) y;
        !           257: if z and x do not interfere and z has no effects not undone by y.
        !           258: This is desirable if z is faster than jumping.
        !           259: 
        !           260: * For a two-insn loop on the 68020, such as
        !           261:   foo: movb    a2@+,a3@+
        !           262:        jne     foo
        !           263: it is better to insert dbeq d0,foo before the jne.
        !           264: d0 can be a junk register.  The challenge is to fit this into
        !           265: a portable framework: when can you detect this situation and
        !           266: still be able to allocate a junk register?
        !           267: 
        !           268: 2. Simpler porting.
        !           269: 
        !           270: Right now, describing the target machine's instructions is done
        !           271: cleanly, but describing its addressing mode is done with several
        !           272: ad-hoc macro definitions.  Porting would be much easier if there were
        !           273: an RTL description for addressing modes like that for instructions.
        !           274: Tools analogous to genflags and genrecog would generate macros from
        !           275: this description.
        !           276: 
        !           277: There would be one pattern in the address-description file for each
        !           278: kind of addressing, and this pattern would have:
        !           279: 
        !           280:   * the RTL expression for the address
        !           281:   * C code to verify its validity (since that may depend on
        !           282:     the exact data).
        !           283:   * C code to print the address in assembler language.
        !           284:   * C code to convert the address into a valid one, if it is not valid.
        !           285:     (This would replace LEGITIMIZE_ADDRESS).
        !           286:   * Register constraints for all indeterminates that appear
        !           287:     in the RTL expression.
        !           288: 
        !           289: 3. Other languages.
        !           290: 
        !           291: Front ends for Pascal, Fortran, Algol, Cobol, Modula-2 and Ada are
        !           292: desirable.
        !           293: 
        !           294: Pascal, Modula-2 and Ada require the implementation of functions
        !           295: within functions.  Some of the mechanisms for this already exist.
        !           296: 
        !           297: 4. More extensions.
        !           298: 
        !           299: * Generated unique labels.  Have some way of generating distinct labels
        !           300: for use in extended asm statements.  I don't know what a good syntax would
        !           301: be.
        !           302: 
        !           303: * A way of defining a structure containing a union, in which the choice of
        !           304: union alternative is controlled by a previous structure component.
        !           305: 
        !           306: Here is a possible syntax for this.
        !           307: 
        !           308: struct foo {
        !           309:   enum { INT, DOUBLE } code;
        !           310:   auto union { case INT: int i; case DOUBLE: double d;} value : code;
        !           311: };
        !           312: 
        !           313: * Allow constructor expressions as lvalues, like this:
        !           314: 
        !           315:        (struct foo) {a, b, c} = foo();
        !           316: 
        !           317: This would call foo, which returns a structure, and then store the
        !           318: several components of the structure into the variables a, b, and c.
        !           319: 
        !           320: 5. Generalize the machine model.
        !           321: 
        !           322: * Some new compiler features may be needed to do a good job on machines
        !           323: where static data needs to be addressed using base registers.
        !           324: 
        !           325: * Some machines have two stacks in different areas of memory, one used
        !           326: for scalars and another for large objects.  The compiler does not
        !           327: now have a way to understand this.
        !           328: 
        !           329: 6. Useful warnings.
        !           330: 
        !           331: * Warn about statements that are undefined because the order of
        !           332: evaluation of increment operators makes a big difference.  Here is an
        !           333: example:
        !           334: 
        !           335:     *foo++ = hack (*foo);
        !           336: 
        !           337: 7. Better documentation of how GCC works and how to port it.
        !           338: 
        !           339: Here is an outline proposed by Allan Adler.
        !           340: 
        !           341: I.    Overview of this document
        !           342: II.   The machines on which GCC is implemented
        !           343:     A. Prose description of those characteristics of target machines and
        !           344:        their operating systems which are pertinent to the implementation
        !           345:        of GCC.
        !           346:        i. target machine characteristics
        !           347:        ii. comparison of this system of machine characteristics with
        !           348:            other systems of machine specification currently in use
        !           349:     B. Tables of the characteristics of the target machines on which
        !           350:        GCC is implemented.
        !           351:     C. A priori restrictions on the values of characteristics of target 
        !           352:        machines, with special reference to those parts of the source code
        !           353:        which entail those restrictions
        !           354:        i. restrictions on individual characteristics 
        !           355:         ii. restrictions involving relations between various characteristics
        !           356:     D. The use of GCC as a cross-compiler 
        !           357:        i. cross-compilation to existing machines
        !           358:        ii. cross-compilation to non-existent machines
        !           359:     E. Assumptions which are made regarding the target machine
        !           360:        i.  assumptions regarding the architecture of the target machine
        !           361:        ii. assumptions regarding the operating system of the target machine
        !           362:        iii. assumptions regarding software resident on the target machine
        !           363:        iv. where in the source code these assumptions are in effect made
        !           364: III.   A systematic approach to writing the files tm.h and xm.h
        !           365:     A. Macros which require special care or skill
        !           366:     B. Examples, with special reference to the underlying reasoning
        !           367: IV.    A systematic approach to writing the machine description file md
        !           368:     A. Minimal viable sets of insn descriptions
        !           369:     B. Examples, with special reference to the underlying reasoning
        !           370: V.     Uses of the file aux-output.c
        !           371: VI.    Specification of what constitutes correct performance of an 
        !           372:        implementation of GCC
        !           373:     A. The components of GCC
        !           374:     B. The itinerary of a C program through GCC
        !           375:     C. A system of benchmark programs
        !           376:     D. What your RTL and assembler should look like with these benchmarks
        !           377:     E. Fine tuning for speed and size of compiled code
        !           378: VII.   A systematic procedure for debugging an implementation of GCC
        !           379:     A. Use of GDB
        !           380:        i. the macros in the file .gdbinit for GCC
        !           381:        ii. obstacles to the use of GDB
        !           382:            a. functions implemented as macros can't be called in GDB
        !           383:     B. Debugging without GDB
        !           384:        i. How to turn off the normal operation of GCC and access specific
        !           385:           parts of GCC
        !           386:     C. Debugging tools
        !           387:     D. Debugging the parser
        !           388:        i. how machine macros and insn definitions affect the parser
        !           389:     E. Debugging the recognizer
        !           390:        i. how machine macros and insn definitions affect the recognizer
        !           391: 
        !           392: ditto for other components
        !           393: 
        !           394: VIII. Data types used by GCC, with special reference to restrictions not 
        !           395:       specified in the formal definition of the data type
        !           396: IX.   References to the literature for the algorithms used in GCC
        !           397: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.