Mercurial > hg > CbC > CbC_gcc
comparison gcc/doc/passes.texi @ 19:58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
author | kent@firefly.cr.ie.u-ryukyu.ac.jp |
---|---|
date | Thu, 24 Sep 2009 13:21:57 +0900 |
parents | a06113de4d67 |
children | 77e2b8dfacca |
comparison
equal
deleted
inserted
replaced
18:33936f7f2835 | 19:58ad6c70ea60 |
---|---|
19 | 19 |
20 @menu | 20 @menu |
21 * Parsing pass:: The language front end turns text into bits. | 21 * Parsing pass:: The language front end turns text into bits. |
22 * Gimplification pass:: The bits are turned into something we can optimize. | 22 * Gimplification pass:: The bits are turned into something we can optimize. |
23 * Pass manager:: Sequencing the optimization passes. | 23 * Pass manager:: Sequencing the optimization passes. |
24 * Tree-SSA passes:: Optimizations on a high-level representation. | 24 * Tree SSA passes:: Optimizations on a high-level representation. |
25 * RTL passes:: Optimizations on a low-level representation. | 25 * RTL passes:: Optimizations on a low-level representation. |
26 @end menu | 26 @end menu |
27 | 27 |
28 @node Parsing pass | 28 @node Parsing pass |
29 @section Parsing pass | 29 @section Parsing pass |
92 @code{rest_of_decl_compilation}. Each complete type definition should | 92 @code{rest_of_decl_compilation}. Each complete type definition should |
93 be passed to @code{rest_of_type_compilation}. Each function definition | 93 be passed to @code{rest_of_type_compilation}. Each function definition |
94 should be passed to @code{cgraph_finalize_function}. | 94 should be passed to @code{cgraph_finalize_function}. |
95 | 95 |
96 TODO: I know rest_of_compilation currently has all sorts of | 96 TODO: I know rest_of_compilation currently has all sorts of |
97 rtl-generation semantics. I plan to move all code generation | 97 RTL generation semantics. I plan to move all code generation |
98 bits (both tree and rtl) to compile_function. Should we hide | 98 bits (both Tree and RTL) to compile_function. Should we hide |
99 cgraph from the front ends and move back to rest_of_compilation | 99 cgraph from the front ends and move back to rest_of_compilation |
100 as the official interface? Possibly we should rename all three | 100 as the official interface? Possibly we should rename all three |
101 interfaces such that the names match in some meaningful way and | 101 interfaces such that the names match in some meaningful way and |
102 that is more descriptive than "rest_of". | 102 that is more descriptive than "rest_of". |
103 | 103 |
170 Passes without any names, or with a name starting with a star, do not | 170 Passes without any names, or with a name starting with a star, do not |
171 dump anything. | 171 dump anything. |
172 | 172 |
173 TODO: describe the global variables set up by the pass manager, | 173 TODO: describe the global variables set up by the pass manager, |
174 and a brief description of how a new pass should use it. | 174 and a brief description of how a new pass should use it. |
175 I need to look at what info rtl passes use first@enddots{} | 175 I need to look at what info RTL passes use first@enddots{} |
176 | 176 |
177 @node Tree-SSA passes | 177 @node Tree SSA passes |
178 @section Tree-SSA passes | 178 @section Tree SSA passes |
179 | 179 |
180 The following briefly describes the tree optimization passes that are | 180 The following briefly describes the Tree optimization passes that are |
181 run after gimplification and what source files they are located in. | 181 run after gimplification and what source files they are located in. |
182 | 182 |
183 @itemize @bullet | 183 @itemize @bullet |
184 @item Remove useless statements | 184 @item Remove useless statements |
185 | 185 |
399 and described by @code{pass_loop}. | 399 and described by @code{pass_loop}. |
400 | 400 |
401 The optimizations performed by this pass are: | 401 The optimizations performed by this pass are: |
402 | 402 |
403 Loop invariant motion. This pass moves only invariants that | 403 Loop invariant motion. This pass moves only invariants that |
404 would be hard to handle on rtl level (function calls, operations that expand to | 404 would be hard to handle on RTL level (function calls, operations that expand to |
405 nontrivial sequences of insns). With @option{-funswitch-loops} it also moves | 405 nontrivial sequences of insns). With @option{-funswitch-loops} it also moves |
406 operands of conditions that are invariant out of the loop, so that we can use | 406 operands of conditions that are invariant out of the loop, so that we can use |
407 just trivial invariantness analysis in loop unswitching. The pass also includes | 407 just trivial invariantness analysis in loop unswitching. The pass also includes |
408 store motion. The pass is implemented in @file{tree-ssa-loop-im.c}. | 408 store motion. The pass is implemented in @file{tree-ssa-loop-im.c}. |
409 | 409 |
420 | 420 |
421 Loop unswitching. This pass moves the conditional jumps that are invariant | 421 Loop unswitching. This pass moves the conditional jumps that are invariant |
422 out of the loops. To achieve this, a duplicate of the loop is created for | 422 out of the loops. To achieve this, a duplicate of the loop is created for |
423 each possible outcome of conditional jump(s). The pass is implemented in | 423 each possible outcome of conditional jump(s). The pass is implemented in |
424 @file{tree-ssa-loop-unswitch.c}. This pass should eventually replace the | 424 @file{tree-ssa-loop-unswitch.c}. This pass should eventually replace the |
425 rtl-level loop unswitching in @file{loop-unswitch.c}, but currently | 425 RTL level loop unswitching in @file{loop-unswitch.c}, but currently |
426 the rtl-level pass is not completely redundant yet due to deficiencies | 426 the RTL level pass is not completely redundant yet due to deficiencies |
427 in tree level alias analysis. | 427 in tree level alias analysis. |
428 | 428 |
429 The optimizations also use various utility functions contained in | 429 The optimizations also use various utility functions contained in |
430 @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and | 430 @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and |
431 @file{cfgloopmanip.c}. | 431 @file{cfgloopmanip.c}. |
649 @end itemize | 649 @end itemize |
650 | 650 |
651 @node RTL passes | 651 @node RTL passes |
652 @section RTL passes | 652 @section RTL passes |
653 | 653 |
654 The following briefly describes the rtl generation and optimization | 654 The following briefly describes the RTL generation and optimization |
655 passes that are run after tree optimization. | 655 passes that are run after the Tree optimization passes. |
656 | 656 |
657 @itemize @bullet | 657 @itemize @bullet |
658 @item RTL generation | 658 @item RTL generation |
659 | 659 |
660 @c Avoiding overfull is tricky here. | 660 @c Avoiding overfull is tricky here. |
677 The header files @file{insn-flags.h} and @file{insn-codes.h}, | 677 The header files @file{insn-flags.h} and @file{insn-codes.h}, |
678 generated from the machine description by the programs @code{genflags} | 678 generated from the machine description by the programs @code{genflags} |
679 and @code{gencodes}, tell this pass which standard names are available | 679 and @code{gencodes}, tell this pass which standard names are available |
680 for use and which patterns correspond to them. | 680 for use and which patterns correspond to them. |
681 | 681 |
682 @item Generate exception handling landing pads | 682 @item Generation of exception landing pads |
683 | 683 |
684 This pass generates the glue that handles communication between the | 684 This pass generates the glue that handles communication between the |
685 exception handling library routines and the exception handlers within | 685 exception handling library routines and the exception handlers within |
686 the function. Entry points in the function that are invoked by the | 686 the function. Entry points in the function that are invoked by the |
687 exception handling library are called @dfn{landing pads}. The code | 687 exception handling library are called @dfn{landing pads}. The code |
688 for this pass is located within @file{except.c}. | 688 for this pass is located in @file{except.c}. |
689 | 689 |
690 @item Cleanup control flow graph | 690 @item Control flow graph cleanup |
691 | 691 |
692 This pass removes unreachable code, simplifies jumps to next, jumps to | 692 This pass removes unreachable code, simplifies jumps to next, jumps to |
693 jump, jumps across jumps, etc. The pass is run multiple times. | 693 jump, jumps across jumps, etc. The pass is run multiple times. |
694 For historical reasons, it is occasionally referred to as the ``jump | 694 For historical reasons, it is occasionally referred to as the ``jump |
695 optimization pass''. The bulk of the code for this pass is in | 695 optimization pass''. The bulk of the code for this pass is in |
700 | 700 |
701 This pass attempts to remove redundant computation by substituting | 701 This pass attempts to remove redundant computation by substituting |
702 variables that come from a single definition, and | 702 variables that come from a single definition, and |
703 seeing if the result can be simplified. It performs copy propagation | 703 seeing if the result can be simplified. It performs copy propagation |
704 and addressing mode selection. The pass is run twice, with values | 704 and addressing mode selection. The pass is run twice, with values |
705 being propagated into loops only on the second run. It is located in | 705 being propagated into loops only on the second run. The code is |
706 @file{fwprop.c}. | 706 located in @file{fwprop.c}. |
707 | 707 |
708 @item Common subexpression elimination | 708 @item Common subexpression elimination |
709 | 709 |
710 This pass removes redundant computation within basic blocks, and | 710 This pass removes redundant computation within basic blocks, and |
711 optimizes addressing modes based on cost. The pass is run twice. | 711 optimizes addressing modes based on cost. The pass is run twice. |
712 The source is located in @file{cse.c}. | 712 The code for this pass is located in @file{cse.c}. |
713 | 713 |
714 @item Global common subexpression elimination. | 714 @item Global common subexpression elimination |
715 | 715 |
716 This pass performs two | 716 This pass performs two |
717 different types of GCSE depending on whether you are optimizing for | 717 different types of GCSE depending on whether you are optimizing for |
718 size or not (LCM based GCSE tends to increase code size for a gain in | 718 size or not (LCM based GCSE tends to increase code size for a gain in |
719 speed, while Morel-Renvoise based GCSE does not). | 719 speed, while Morel-Renvoise based GCSE does not). |
753 | 753 |
754 This pass attempts to replace conditional branches and surrounding | 754 This pass attempts to replace conditional branches and surrounding |
755 assignments with arithmetic, boolean value producing comparison | 755 assignments with arithmetic, boolean value producing comparison |
756 instructions, and conditional move instructions. In the very last | 756 instructions, and conditional move instructions. In the very last |
757 invocation after reload, it will generate predicated instructions | 757 invocation after reload, it will generate predicated instructions |
758 when supported by the target. The pass is located in @file{ifcvt.c}. | 758 when supported by the target. The code is located in @file{ifcvt.c}. |
759 | 759 |
760 @item Web construction | 760 @item Web construction |
761 | 761 |
762 This pass splits independent uses of each pseudo-register. This can | 762 This pass splits independent uses of each pseudo-register. This can |
763 improve effect of the other transformation, such as CSE or register | 763 improve effect of the other transformation, such as CSE or register |
764 allocation. Its source files are @file{web.c}. | 764 allocation. The code for this pass is located in @file{web.c}. |
765 | |
766 @item Life analysis | |
767 | |
768 This pass computes which pseudo-registers are live at each point in | |
769 the program, and makes the first instruction that uses a value point | |
770 at the instruction that computed the value. It then deletes | |
771 computations whose results are never used, and combines memory | |
772 references with add or subtract instructions to make autoincrement or | |
773 autodecrement addressing. The pass is located in @file{flow.c}. | |
774 | 765 |
775 @item Instruction combination | 766 @item Instruction combination |
776 | 767 |
777 This pass attempts to combine groups of two or three instructions that | 768 This pass attempts to combine groups of two or three instructions that |
778 are related by data flow into single instructions. It combines the | 769 are related by data flow into single instructions. It combines the |
779 RTL expressions for the instructions by substitution, simplifies the | 770 RTL expressions for the instructions by substitution, simplifies the |
780 result using algebra, and then attempts to match the result against | 771 result using algebra, and then attempts to match the result against |
781 the machine description. The pass is located in @file{combine.c}. | 772 the machine description. The code is located in @file{combine.c}. |
782 | 773 |
783 @item Register movement | 774 @item Register movement |
784 | 775 |
785 This pass looks for cases where matching constraints would force an | 776 This pass looks for cases where matching constraints would force an |
786 instruction to need a reload, and this reload would be a | 777 instruction to need a reload, and this reload would be a |
787 register-to-register move. It then attempts to change the registers | 778 register-to-register move. It then attempts to change the registers |
788 used by the instruction to avoid the move instruction. | 779 used by the instruction to avoid the move instruction. The code is |
789 The pass is located in @file{regmove.c}. | 780 located in @file{regmove.c}. |
790 | 781 |
791 @item Optimize mode switching | 782 @item Mode switching optimization |
792 | 783 |
793 This pass looks for instructions that require the processor to be in a | 784 This pass looks for instructions that require the processor to be in a |
794 specific ``mode'' and minimizes the number of mode changes required to | 785 specific ``mode'' and minimizes the number of mode changes required to |
795 satisfy all users. What these modes are, and what they apply to are | 786 satisfy all users. What these modes are, and what they apply to are |
796 completely target-specific. | 787 completely target-specific. The code for this pass is located in |
797 The source is located in @file{mode-switching.c}. | 788 @file{mode-switching.c}. |
798 | 789 |
799 @cindex modulo scheduling | 790 @cindex modulo scheduling |
800 @cindex sms, swing, software pipelining | 791 @cindex sms, swing, software pipelining |
801 @item Modulo scheduling | 792 @item Modulo scheduling |
802 | 793 |
803 This pass looks at innermost loops and reorders their instructions | 794 This pass looks at innermost loops and reorders their instructions |
804 by overlapping different iterations. Modulo scheduling is performed | 795 by overlapping different iterations. Modulo scheduling is performed |
805 immediately before instruction scheduling. | 796 immediately before instruction scheduling. The code for this pass is |
806 The pass is located in (@file{modulo-sched.c}). | 797 located in @file{modulo-sched.c}. |
807 | 798 |
808 @item Instruction scheduling | 799 @item Instruction scheduling |
809 | 800 |
810 This pass looks for instructions whose output will not be available by | 801 This pass looks for instructions whose output will not be available by |
811 the time that it is used in subsequent instructions. Memory loads and | 802 the time that it is used in subsequent instructions. Memory loads and |
812 floating point instructions often have this behavior on RISC machines. | 803 floating point instructions often have this behavior on RISC machines. |
813 It re-orders instructions within a basic block to try to separate the | 804 It re-orders instructions within a basic block to try to separate the |
814 definition and use of items that otherwise would cause pipeline | 805 definition and use of items that otherwise would cause pipeline |
815 stalls. This pass is performed twice, before and after register | 806 stalls. This pass is performed twice, before and after register |
816 allocation. The pass is located in @file{haifa-sched.c}, | 807 allocation. The code for this pass is located in @file{haifa-sched.c}, |
817 @file{sched-deps.c}, @file{sched-ebb.c}, @file{sched-rgn.c} and | 808 @file{sched-deps.c}, @file{sched-ebb.c}, @file{sched-rgn.c} and |
818 @file{sched-vis.c}. | 809 @file{sched-vis.c}. |
819 | 810 |
820 @item Register allocation | 811 @item Register allocation |
821 | 812 |
882 | 873 |
883 This pass computes where the variables are stored at each | 874 This pass computes where the variables are stored at each |
884 position in code and generates notes describing the variable locations | 875 position in code and generates notes describing the variable locations |
885 to RTL code. The location lists are then generated according to these | 876 to RTL code. The location lists are then generated according to these |
886 notes to debug information if the debugging information format supports | 877 notes to debug information if the debugging information format supports |
887 location lists. | 878 location lists. The code is located in @file{var-tracking.c}. |
888 | 879 |
889 @item Delayed branch scheduling | 880 @item Delayed branch scheduling |
890 | 881 |
891 This optional pass attempts to find instructions that can go into the | 882 This optional pass attempts to find instructions that can go into the |
892 delay slots of other instructions, usually jumps and calls. The | 883 delay slots of other instructions, usually jumps and calls. The code |
893 source file name is @file{reorg.c}. | 884 for this pass is located in @file{reorg.c}. |
894 | 885 |
895 @item Branch shortening | 886 @item Branch shortening |
896 | 887 |
897 On many RISC machines, branch instructions have a limited range. | 888 On many RISC machines, branch instructions have a limited range. |
898 Thus, longer sequences of instructions must be used for long branches. | 889 Thus, longer sequences of instructions must be used for long branches. |
899 In this pass, the compiler figures out what how far each instruction | 890 In this pass, the compiler figures out what how far each instruction |
900 will be from each other instruction, and therefore whether the usual | 891 will be from each other instruction, and therefore whether the usual |
901 instructions, or the longer sequences, must be used for each branch. | 892 instructions, or the longer sequences, must be used for each branch. |
893 The code for this pass is located in @file{final.c}. | |
902 | 894 |
903 @item Register-to-stack conversion | 895 @item Register-to-stack conversion |
904 | 896 |
905 Conversion from usage of some hard registers to usage of a register | 897 Conversion from usage of some hard registers to usage of a register |
906 stack may be done at this point. Currently, this is supported only | 898 stack may be done at this point. Currently, this is supported only |
907 for the floating-point registers of the Intel 80387 coprocessor. The | 899 for the floating-point registers of the Intel 80387 coprocessor. The |
908 source file name is @file{reg-stack.c}. | 900 code for this pass is located in @file{reg-stack.c}. |
909 | 901 |
910 @item Final | 902 @item Final |
911 | 903 |
912 This pass outputs the assembler code for the function. The source files | 904 This pass outputs the assembler code for the function. The source files |
913 are @file{final.c} plus @file{insn-output.c}; the latter is generated | 905 are @file{final.c} plus @file{insn-output.c}; the latter is generated |