diff options
author | mmitchel <mmitchel@138bc75d-0d04-0410-961f-82ee72b054a4> | 2000-08-02 04:21:27 +0000 |
---|---|---|
committer | mmitchel <mmitchel@138bc75d-0d04-0410-961f-82ee72b054a4> | 2000-08-02 04:21:27 +0000 |
commit | 1deb248ef2fc317c1131553bd35ae9e2271882ab (patch) | |
tree | effa31090707b8e4d80bb9f56140fd2884c53bc1 | |
parent | 76c0b418e85d653b0fbdb1f9c5e6cd0150a760d5 (diff) | |
download | gcc-1deb248ef2fc317c1131553bd35ae9e2271882ab.tar.gz |
* Makefile.in (OBJS): Added dce.o.
(ssa.o): Updated target to include ssa.h.
(flow.o): Likewise.
(toplev.o): Likewise.
(dce.o): Created target.
* basic-block.h: Added comments.
(INVALID_BLOCK): Added definition.
(connect_infinite_loops_to_exit): Added declaration.
Moved SSA declarations to ssa.h.
* flow.c: Added inclusion of ssa.h.
(struct depth_first_search_dsS, depth_first_search_ds):
Added definitions.
(compute_immediate_postdominators): Added definition.
(connect_infinite_loops_to_exit): Likewise.
(flow_dfs_compute_reverse_init): Likewise.
(flow_dfs_compute_reverse_add_bb): Likewise.
(flow_dfs_compute_reverse_execute): Likewise.
(flow_dfs_compute_reverse_finish): Likewise.
* rtl.h (rtx/in_struct): Added use to determine insn necessity.
(LABEL_P): Added definition.
(JUMP_P): Likewise.
(NOTE_P): Likewise.
(BARRIER_P): Likewise.
(JUMP_TABLE_DATA_P): Likewise.
(INSN_DEAD_CODE_P): Likewise.
* ssa.c: Replaced inclusions with ssa.h inclusion.
(CONVERT_HARD_REGISTER_TO_SSA_P): Moved to ssa.h.
(rename_registers): Removed unnecessary variables.
* ssa.h: Created by moving declarations from ssa.c and
basic-block.h.
* timevar.def: Defined TV_DEAD_CODE_ELIM.
* toplev.c: Added ssa.h inclusion.
(dump_file_index): Added DFI_dce.
(dump_file): Added "dce" entry.
Defined flag_ssa.
(f_options): Added dce entry.
* invoke.texi: Document -fdce. Emphasize experimental status of
-fssa.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@35419 138bc75d-0d04-0410-961f-82ee72b054a4
-rw-r--r-- | gcc/ChangeLog | 42 | ||||
-rw-r--r-- | gcc/Makefile.in | 15 | ||||
-rw-r--r-- | gcc/basic-block.h | 25 | ||||
-rw-r--r-- | gcc/dce.c | 620 | ||||
-rw-r--r-- | gcc/flow.c | 175 | ||||
-rw-r--r-- | gcc/invoke.texi | 11 | ||||
-rw-r--r-- | gcc/rtl.h | 27 | ||||
-rw-r--r-- | gcc/ssa.c | 49 | ||||
-rw-r--r-- | gcc/ssa.h | 64 | ||||
-rw-r--r-- | gcc/timevar.def | 1 | ||||
-rw-r--r-- | gcc/toplev.c | 26 |
11 files changed, 990 insertions, 65 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cf7a1e2879b..2d752242698 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,45 @@ +2000-08-01 Jeffrey Oldham <oldham@codesourcery.com> + Mark Mitchell <mark@codesourcery.com> + + * Makefile.in (OBJS): Added dce.o. + (ssa.o): Updated target to include ssa.h. + (flow.o): Likewise. + (toplev.o): Likewise. + (dce.o): Created target. + * basic-block.h: Added comments. + (INVALID_BLOCK): Added definition. + (connect_infinite_loops_to_exit): Added declaration. + Moved SSA declarations to ssa.h. + * flow.c: Added inclusion of ssa.h. + (struct depth_first_search_dsS, depth_first_search_ds): + Added definitions. + (compute_immediate_postdominators): Added definition. + (connect_infinite_loops_to_exit): Likewise. + (flow_dfs_compute_reverse_init): Likewise. + (flow_dfs_compute_reverse_add_bb): Likewise. + (flow_dfs_compute_reverse_execute): Likewise. + (flow_dfs_compute_reverse_finish): Likewise. + * rtl.h (rtx/in_struct): Added use to determine insn necessity. + (LABEL_P): Added definition. + (JUMP_P): Likewise. + (NOTE_P): Likewise. + (BARRIER_P): Likewise. + (JUMP_TABLE_DATA_P): Likewise. + (INSN_DEAD_CODE_P): Likewise. + * ssa.c: Replaced inclusions with ssa.h inclusion. + (CONVERT_HARD_REGISTER_TO_SSA_P): Moved to ssa.h. + (rename_registers): Removed unnecessary variables. + * ssa.h: Created by moving declarations from ssa.c and + basic-block.h. + * timevar.def: Defined TV_DEAD_CODE_ELIM. + * toplev.c: Added ssa.h inclusion. + (dump_file_index): Added DFI_dce. + (dump_file): Added "dce" entry. + Defined flag_ssa. + (f_options): Added dce entry. + * invoke.texi: Document -fdce. Emphasize experimental status of + -fssa. + 2000-08-01 Zack Weinberg <zack@wolery.cumb.org> * cpperror.c (v_message): Split into _cpp_begin_message and diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 564cc1d851f..31ab344f9d1 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -696,7 +696,7 @@ OBJS = diagnostic.o \ profile.o insn-attrtab.o $(out_object_file) $(EXTRA_OBJS) convert.o \ mbchar.o splay-tree.o graph.o sbitmap.o resource.o hash.o predict.o \ lists.o ggc-common.o $(GGC) simplify-rtx.o ssa.o bb-reorder.o \ - sibcall.o conflict.o timevar.o ifcvt.o + sibcall.o conflict.o timevar.o ifcvt.o dce.o # GEN files are listed separately, so they can be built before doing parallel # makes for cc1 or cc1plus. Otherwise sequent parallel make attempts to load @@ -1242,7 +1242,7 @@ toplev.o : toplev.c $(CONFIG_H) system.h $(TREE_H) $(RTL_H) function.h \ flags.h input.h $(INSN_ATTR_H) xcoffout.h defaults.h output.h diagnostic.h \ insn-codes.h insn-config.h intl.h $(RECOG_H) Makefile toplev.h dwarfout.h \ dwarf2out.h sdbout.h dbxout.h $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) \ - graph.h loop.h except.h regs.h $(TIMEVAR_H) $(lang_options_files) + graph.h loop.h except.h regs.h $(TIMEVAR_H) $(lang_options_files) ssa.h $(CC) $(ALL_CFLAGS) $(ALL_CPPFLAGS) $(INCLUDES) $(MAYBE_USE_COLLECT2) \ -DTARGET_NAME=\"$(target_alias)\" \ -c `echo $(srcdir)/toplev.c | sed 's,^\./,,'` @@ -1326,10 +1326,11 @@ resource.o : resource.c $(CONFIG_H) $(RTL_H) hard-reg-set.h system.h \ $(INSN_ATTR_H) except.h lcm.o : lcm.c $(CONFIG_H) system.h $(RTL_H) $(REGS_H) hard-reg-set.h flags.h \ real.h insn-config.h $(INSN_ATTR_H) $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) -ssa.o : ssa.c $(CONFIG_H) system.h $(RTL_H) varray.h sbitmap.h \ - $(HASHTAB_H) $(REGS_H) hard-reg-set.h flags.h function.h real.h \ - insn-config.h $(RECOG_H) $(BASIC_BLOCK_H) \ - output.h +ssa.o : ssa.c $(CONFIG_H) system.h $(REGS_H) varray.h \ + hard-reg-set.h flags.h function.h real.h insn-config.h $(RECOG_H) \ + $(BASIC_BLOCK_H) output.h ssa.h +dce.o : dce.c $(CONFIG_H) system.h $(RTL_H) hard-reg-set.h $(BASIC_BLOCK_H) \ + ssa.h insn-config.h $(RECOG_H) output.h conflict.o : conflict.c $(CONFIG_H) system.h $(OBSTACK_H) $(HASHTAB_H) \ $(RTL_H) hard-reg-set.h $(BASIC_BLOCK_H) profile.o : profile.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \ @@ -1345,7 +1346,7 @@ unroll.o : unroll.c $(CONFIG_H) system.h $(RTL_H) insn-config.h function.h \ hard-reg-set.h varray.h $(BASIC_BLOCK_H) flow.o : flow.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h insn-config.h \ $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \ - insn-flags.h function.h except.h $(EXPR_H) + insn-flags.h function.h except.h $(EXPR_H) ssa.h combine.o : combine.c $(CONFIG_H) system.h $(RTL_H) flags.h function.h \ insn-config.h insn-flags.h insn-codes.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \ $(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 2e540758b33..a018f23770b 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -141,6 +141,18 @@ typedef struct edge_def { #define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH) +/* Basic blocks need not start with a label nor end with a jump insn. + For example, a previous basic block may just "conditionally fall" + into the succeeding basic block, and the last basic block need not + end with a jump insn. Block 0 is a descendant of the entry block. + + A basic block beginning with two labels cannot have notes between + the labels. + + Data for jump tables are stored in jump_insns that occur in no + basic block even though these insns can follow or precede insns in + basic blocks. */ + /* Basic block information indexed by block number. */ typedef struct basic_block_def { /* The first and last insns of the block. */ @@ -210,6 +222,9 @@ extern regset regs_live_at_setjmp; #define ENTRY_BLOCK (-1) #define EXIT_BLOCK (-2) +/* Special block number not valid for any block. */ +#define INVALID_BLOCK (-3) + /* Similarly, block pointers for the edge list. */ extern struct basic_block_def entry_exit_blocks[2]; #define ENTRY_BLOCK_PTR (&entry_exit_blocks[0]) @@ -230,6 +245,7 @@ extern void insert_insn_on_edge PARAMS ((rtx, edge)); extern void commit_edge_insertions PARAMS ((void)); extern void remove_fake_edges PARAMS ((void)); extern void add_noreturn_fake_exit_edges PARAMS ((void)); +extern void connect_infinite_loops_to_exit PARAMS ((void)); extern rtx flow_delete_insn PARAMS ((rtx)); extern void flow_delete_insn_chain PARAMS ((rtx, rtx)); extern void make_edge PARAMS ((sbitmap *, basic_block, @@ -514,13 +530,4 @@ extern conflict_graph conflict_graph_compute PARAMS ((regset, partition)); -/* In ssa.c */ -extern void convert_to_ssa PARAMS ((void)); -extern void convert_from_ssa PARAMS ((void)); -typedef int (*successor_phi_fn) PARAMS ((rtx, int, int, void *)); -extern int for_each_successor_phi PARAMS ((basic_block bb, - successor_phi_fn, - void *)); -extern int in_ssa_form; - #endif /* _BASIC_BLOCK_H */ diff --git a/gcc/dce.c b/gcc/dce.c new file mode 100644 index 00000000000..f385afd31ea --- /dev/null +++ b/gcc/dce.c @@ -0,0 +1,620 @@ +/* Dead-code elimination pass for the GNU compiler. + Copyright (C) 2000 Free Software Foundation, Inc. + Written by Jeffrey D. Oldham <oldham@codesourcery.com>. + +This file is part of GNU CC. + +GNU CC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 2, or (at your option) any +later version. + +GNU CC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GNU CC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +/* Dead-code elimination is the removal of instructions which have no + impact on the program's output. "Dead instructions" have no impact + on the program's output, while "necessary instructions" may have + impact on the output. + + The algorithm consists of three phases: + 1) marking as necessary all instructions known to be necessary, + e.g., writing a value to memory, + 2) propagating necessary instructions, e.g., the instructions + giving values to operands in necessary instructions, and + 3) removing dead instructions (except replacing dead conditionals + with unconditional jumps). + + Side Effects: + The last step can require adding labels, deleting insns, and + modifying basic block structures. Some conditional jumps may be + converted to unconditional jumps so the control-flow graph may be + out-of-date. + + Edges from some infinite loops to the exit block can be added to + the control-flow graph. + + It Does Not Perform: + We decided to not simultaneously perform jump optimization and dead + loop removal during dead-code elimination. Thus, all jump + instructions originally present remain after dead-code elimination + but 1) unnecessary conditional jump instructions are changed to + unconditional jump instructions and 2) all unconditional jump + instructions remain. + + Assumptions: + 1) SSA has been performed. + 2) The basic block and control-flow graph structures are accurate. + 3) The flow graph permits constructing an edge_list. + 4) note rtxes should be saved. + + Unfinished: + When replacing unnecessary conditional jumps with unconditional + jumps, the control-flow graph is not updated. It should be. + + References: + Building an Optimizing Compiler + Robert Morgan + Butterworth-Heinemann, 1998 + Section 8.9 +*/ + +#include "config.h" +#include "system.h" + +#include "rtl.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "ssa.h" +#include "insn-config.h" +#include "recog.h" +#include "output.h" + +/* We cannot use <assert.h> in GCC source, since that would include + GCC's assert.h, which may not be compatible with the host compiler. */ +#undef assert +#ifdef NDEBUG +# define assert(e) +#else +# define assert(e) do { if (! (e)) abort (); } while (0) +#endif + +/* A map from blocks to the edges on which they are control dependent. */ +typedef struct { + /* An dynamically allocated array. The Nth element corresponds to + the block with index N + 2. The Ith bit in the bitmap is set if + that block is dependent on the Ith edge. */ + bitmap *data; + /* The number of elements in the array. */ + int length; +} control_dependent_block_to_edge_map_s, *control_dependent_block_to_edge_map; + +/* Local function prototypes. */ +static control_dependent_block_to_edge_map control_dependent_block_to_edge_map_create + PARAMS((size_t num_basic_blocks)); +static void set_control_dependent_block_to_edge_map_bit + PARAMS ((control_dependent_block_to_edge_map c, basic_block bb, + int edge_index)); +static void control_dependent_block_to_edge_map_free + PARAMS ((control_dependent_block_to_edge_map c)); +static void find_all_control_dependences + PARAMS ((struct edge_list *el, int *pdom, + control_dependent_block_to_edge_map cdbte)); +static void find_control_dependence + PARAMS ((struct edge_list *el, int edge_index, int *pdom, + control_dependent_block_to_edge_map cdbte)); +static basic_block find_pdom + PARAMS ((int *pdom, basic_block block)); +static int inherently_necessary_register_1 + PARAMS ((rtx *current_rtx, void *data)); +static int inherently_necessary_register + PARAMS ((rtx current_rtx)); +static int find_inherently_necessary + PARAMS ((rtx current_rtx)); +static int propagate_necessity_through_operand + PARAMS ((rtx *current_rtx, void *data)); + +/* Unnecessary insns are indicated using insns' in_struct bit. */ + +/* Indicate INSN is dead-code; returns nothing. */ +#define KILL_INSN(INSN) INSN_DEAD_CODE_P(INSN) = 1 +/* Indicate INSN is necessary, i.e., not dead-code; returns nothing. */ +#define RESURRECT_INSN(INSN) INSN_DEAD_CODE_P(INSN) = 0 +/* Return nonzero if INSN is unnecessary. */ +#define UNNECESSARY_P(INSN) INSN_DEAD_CODE_P(INSN) +static void mark_all_insn_unnecessary + PARAMS ((void)); +/* Execute CODE with free variable INSN for all unnecessary insns in + an unspecified order, producing no output. */ +#define EXECUTE_IF_UNNECESSARY(INSN, CODE) \ +{ \ + rtx INSN; \ + \ + for (INSN = get_insns (); INSN != NULL_RTX; INSN = NEXT_INSN (INSN)) \ + if (INSN_DEAD_CODE_P (INSN)) { \ + CODE; \ + } \ +} +/* Find the label beginning block BB. */ +static rtx find_block_label + PARAMS ((basic_block bb)); +/* Remove INSN, updating its basic block structure. */ +static void delete_insn_bb + PARAMS ((rtx insn)); + +/* Recording which blocks are control dependent on which edges. We + expect each block to be control dependent on very few edges so we + use a bitmap for each block recording its edges. An array holds + the bitmap. Its position 0 entry holds the bitmap for block + INVALID_BLOCK+1 so that all blocks, including the entry and exit + blocks can participate in the data structure. */ + +/* Create a control_dependent_block_to_edge_map, given the number + NUM_BASIC_BLOCKS of non-entry, non-exit basic blocks, e.g., + n_basic_blocks. This memory must be released using + control_dependent_block_to_edge_map_free (). */ + +static control_dependent_block_to_edge_map +control_dependent_block_to_edge_map_create (num_basic_blocks) + size_t num_basic_blocks; +{ + int i; + control_dependent_block_to_edge_map c + = xmalloc (sizeof (control_dependent_block_to_edge_map_s)); + c->length = num_basic_blocks - (INVALID_BLOCK+1); + c->data = xmalloc ((size_t) c->length*sizeof (bitmap)); + for (i = 0; i < c->length; ++i) + c->data[i] = BITMAP_XMALLOC (); + + return c; +} + +/* Indicate block BB is control dependent on an edge with index + EDGE_INDEX in the mapping C of blocks to edges on which they are + control-dependent. */ + +static void +set_control_dependent_block_to_edge_map_bit (c, bb, edge_index) + control_dependent_block_to_edge_map c; + basic_block bb; + int edge_index; +{ + assert(bb->index - (INVALID_BLOCK+1) < c->length); + bitmap_set_bit (c->data[bb->index - (INVALID_BLOCK+1)], + edge_index); +} + +/* Execute CODE for each edge (given number EDGE_NUMBER within the + CODE) for which the block containing INSN is control dependent, + returning no output. CDBTE is the mapping of blocks to edges on + which they are control-dependent. */ + +#define EXECUTE_IF_CONTROL_DEPENDENT(CDBTE, INSN, EDGE_NUMBER, CODE) \ + EXECUTE_IF_SET_IN_BITMAP \ + (CDBTE->data[BLOCK_NUM (INSN) - (INVALID_BLOCK+1)], 0, \ + EDGE_NUMBER, CODE) + +/* Destroy a control_dependent_block_to_edge_map C. */ + +static void +control_dependent_block_to_edge_map_free (c) + control_dependent_block_to_edge_map c; +{ + int i; + for (i = 0; i < c->length; ++i) + BITMAP_XFREE (c->data[i]); + free ((PTR) c); +} + +/* Record all blocks' control dependences on all edges in the edge + list EL, ala Morgan, Section 3.6. The mapping PDOM of blocks to + their postdominators are used, and results are stored in CDBTE, + which should be empty. */ + +static void +find_all_control_dependences (el, pdom, cdbte) + struct edge_list *el; + int *pdom; + control_dependent_block_to_edge_map cdbte; +{ + int i; + + for (i = 0; i < NUM_EDGES (el); ++i) + find_control_dependence (el, i, pdom, cdbte); +} + +/* Determine all blocks' control dependences on the given edge with + edge_list EL index EDGE_INDEX, ala Morgan, Section 3.6. The + mapping PDOM of blocks to their postdominators are used, and + results are stored in CDBTE, which is assumed to be initialized + with zeros in each (block b', edge) position. */ + +static void +find_control_dependence (el, edge_index, pdom, cdbte) + struct edge_list *el; + int edge_index; + int *pdom; + control_dependent_block_to_edge_map cdbte; +{ + basic_block current_block; + basic_block ending_block; + + assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR); + ending_block = + (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR) + ? BASIC_BLOCK (0) + : find_pdom (pdom, INDEX_EDGE_PRED_BB (el, edge_index)); + + for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index); + current_block != ending_block && current_block != EXIT_BLOCK_PTR; + current_block = find_pdom (pdom, current_block)) + { + set_control_dependent_block_to_edge_map_bit (cdbte, + current_block, + edge_index); + } +} + +/* Find the immediate postdominator PDOM of the specified basic block + BLOCK. This function is necessary because some blocks have + negative numbers. */ + +static basic_block +find_pdom (pdom, block) + int *pdom; + basic_block block; +{ + assert (block != NULL); + assert (block->index != INVALID_BLOCK); + if (block == ENTRY_BLOCK_PTR) + return BASIC_BLOCK (0); + else if (block == EXIT_BLOCK_PTR || pdom[block->index] == EXIT_BLOCK) + return EXIT_BLOCK_PTR; + else + return BASIC_BLOCK (pdom[block->index]); +} + +/* Determine if the given CURRENT_RTX uses a hard register not + converted to SSA. Returns nonzero only if it uses such a hard + register. DATA is not used. + + The program counter (PC) is not considered inherently necessary + since code should be position-independent and thus not depend on + particular PC values. */ + +static int +inherently_necessary_register_1 (current_rtx, data) + rtx *current_rtx; + void *data ATTRIBUTE_UNUSED; +{ + rtx x = *current_rtx; + + if (x == NULL_RTX) + return 0; + switch (GET_CODE (x)) + { + case CLOBBER: + /* Do not traverse the rest of the clobber. */ + return -1; + break; + case PC: + return 0; + break; + case REG: + if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) || x == pc_rtx) + return 0; + else + return !0; + break; + default: + return 0; + break; + } +} + +/* Return nonzero if the insn CURRENT_RTX is inherently necessary. */ + +static int +inherently_necessary_register (current_rtx) + rtx current_rtx; +{ + return for_each_rtx (¤t_rtx, + &inherently_necessary_register_1, NULL); +} + +/* Mark X as inherently necessary if appropriate. For example, + function calls and storing values into memory are inherently + necessary. This function is to be used with for_each_rtx (). + Return nonzero iff inherently necessary. */ + +static int +find_inherently_necessary (x) + rtx x; +{ + rtx pattern; + if (x == NULL_RTX) + return 0; + else if (inherently_necessary_register (x)) + return !0; + else + switch (GET_CODE (x)) + { + case CALL_INSN: + case CODE_LABEL: + case NOTE: + case BARRIER: + return !0; + break; + case JUMP_INSN: + return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0; + break; + case INSN: + pattern = PATTERN (x); + switch (GET_CODE (pattern)) + { + case SET: + case PRE_DEC: + case PRE_INC: + case POST_DEC: + case POST_INC: + return GET_CODE (SET_DEST (pattern)) == MEM; + case CALL: + case RETURN: + case USE: + case CLOBBER: + return !0; + break; + case ASM_INPUT: + /* We treat assembler instructions as inherently + necessary, and we hope that its operands do not need to + be propagated. */ + return !0; + break; + default: + return 0; + } + default: + /* Found an impossible insn type. */ + abort(); + break; + } +} + +/* Propagate necessity through REG and SUBREG operands of CURRENT_RTX. + This function is called with for_each_rtx () on necessary + instructions. The DATA must be a varray of unprocessed + instructions. */ + +static int +propagate_necessity_through_operand (current_rtx, data) + rtx *current_rtx; + void *data; +{ + rtx x = *current_rtx; + varray_type *unprocessed_instructions = (varray_type *) data; + + if (x == NULL_RTX) + return 0; + switch ( GET_CODE (x)) + { + case REG: + if (CONVERT_REGISTER_TO_SSA_P (REGNO (x))) + { + rtx insn = VARRAY_RTX (ssa_definition, REGNO (x)); + if (insn != NULL_RTX && UNNECESSARY_P (insn)) + { + RESURRECT_INSN (insn); + VARRAY_PUSH_RTX (*unprocessed_instructions, insn); + } + } + return 0; + + default: + return 0; + } +} + +/* Indicate all insns initially assumed to be unnecessary. */ + +static void +mark_all_insn_unnecessary () +{ + rtx insn; + for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn)) + KILL_INSN (insn); +} + +/* Find the label beginning block BB, adding one if necessary. */ + +static rtx +find_block_label (bb) + basic_block bb; +{ + rtx insn = bb->head; + if (LABEL_P (insn)) + return insn; + else + { + rtx new_label = emit_label_before (gen_label_rtx (), insn); + if (insn == bb->head) + bb->head = new_label; + return new_label; + } +} + +/* Remove INSN, updating its basic block structure. */ + +static void +delete_insn_bb (insn) + rtx insn; +{ + basic_block bb; + assert (insn != NULL_RTX); + bb = BLOCK_FOR_INSN (insn); + assert (bb != 0); + if (bb->head == bb->end) + { + /* Delete the insn by converting it to a note. */ + PUT_CODE (insn, NOTE); + NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; + return; + } + else if (insn == bb->head) + bb->head = NEXT_INSN (insn); + else if (insn == bb->end) + bb->end = PREV_INSN (insn); + delete_insn (insn); +} + +/* Perform the dead-code elimination. */ + +void +eliminate_dead_code () +{ + int i; + rtx insn; + /* Necessary instructions with operands to explore. */ + varray_type unprocessed_instructions; + /* Map element (b,e) is nonzero if the block is control dependent on + edge. "cdbte" abbreviates control dependent block to edge. */ + control_dependent_block_to_edge_map cdbte; + sbitmap *postdominators; + /* Element I is the immediate postdominator of block I. */ + int *pdom; + struct edge_list *el; + + int max_insn_uid = get_max_uid (); + + /* Initialize the data structures. */ + mark_all_insn_unnecessary (); + VARRAY_RTX_INIT (unprocessed_instructions, 64, + "unprocessed instructions"); + cdbte = control_dependent_block_to_edge_map_create (n_basic_blocks); + + /* Prepare for use of BLOCK_NUM (). */ + connect_infinite_loops_to_exit (); + /* Be careful not to clear the added edges. */ + compute_bb_for_insn (max_insn_uid); + + /* Compute control dependence. */ + postdominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); + compute_flow_dominators (NULL, postdominators); + pdom = (int *) xmalloc (n_basic_blocks * sizeof (int)); + for (i = 0; i < n_basic_blocks; ++i) + pdom[i] = INVALID_BLOCK; + compute_immediate_postdominators (pdom, postdominators); + /* Assume there is a path from each node to the exit block. */ + for (i = 0; i < n_basic_blocks; ++i) + if (pdom[i] == INVALID_BLOCK) + pdom[i] = EXIT_BLOCK; + sbitmap_vector_free (postdominators); + el = create_edge_list(); + find_all_control_dependences (el, pdom, cdbte); + + /* Find inherently necessary instructions. */ + for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn)) + if (find_inherently_necessary (insn)) + { + RESURRECT_INSN (insn); + VARRAY_PUSH_RTX (unprocessed_instructions, insn); + } + + /* Propagate necessity using the operands of necessary instructions. */ + while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0) + { + rtx current_instruction; + int edge_number; + + current_instruction = VARRAY_TOP_RTX (unprocessed_instructions); + VARRAY_POP (unprocessed_instructions); + + /* Make corresponding control dependent edges necessary. */ + /* Assume the only JUMP_INSN is the block's last insn. It appears + that the last instruction of the program need not be a + JUMP_INSN. */ + + if (INSN_P (current_instruction) + && !JUMP_TABLE_DATA_P (current_instruction)) + { + /* Notes and labels contain no interesting operands. */ + EXECUTE_IF_CONTROL_DEPENDENT + (cdbte, current_instruction, edge_number, + { + rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end; + if (GET_CODE (jump_insn) == JUMP_INSN && + UNNECESSARY_P (jump_insn)) { + RESURRECT_INSN (jump_insn); + VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn); + } + }); + + /* Propagate through the operands. */ + for_each_rtx (¤t_instruction, + &propagate_necessity_through_operand, + (PTR) &unprocessed_instructions); + + } + } + + /* Remove the unnecessary instructions. */ + EXECUTE_IF_UNNECESSARY (insn, + { + if (any_condjump_p (insn)) + { + /* Convert unnecessary conditional insn to an unconditional + jump to immediate postdominator block. */ + rtx old_label = JUMP_LABEL (insn); + int pdom_block_number = + find_pdom (pdom, BLOCK_FOR_INSN (insn))->index; + + /* Prevent the conditional jump's label from being deleted so + we do not have to modify the basic block structure. */ + ++LABEL_NUSES (old_label); + + if (pdom_block_number != EXIT_BLOCK + && pdom_block_number != INVALID_BLOCK) + { + rtx lbl = find_block_label (BASIC_BLOCK (pdom_block_number)); + rtx new_jump = emit_jump_insn_before (gen_jump (lbl), insn); + + /* Let jump know that label is in use. */ + JUMP_LABEL (new_jump) = lbl; + ++LABEL_NUSES (lbl); + + delete_insn_bb (insn); + + /* A conditional branch is unnecessary if and only if any + block control-dependent on it is unnecessary. Thus, + any phi nodes in these unnecessary blocks are also + removed and these nodes need not be updated. */ + + /* A barrier must follow any unconditional jump. Barriers + are not in basic blocks so this must occur after + deleting the conditional jump. */ + emit_barrier_after (new_jump); + } + else + /* The block drops off the end of the function and the + ending conditional jump is not needed. */ + delete_insn_bb (insn); + } + else if (!JUMP_P (insn)) + delete_insn_bb (insn); + }); + + /* Release allocated memory. */ + for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn)) + RESURRECT_INSN (insn); + assert (VARRAY_ACTIVE_SIZE(unprocessed_instructions) == 0); + VARRAY_FREE (unprocessed_instructions); + control_dependent_block_to_edge_map_free (cdbte); + free ((PTR) pdom); + free_edge_list (el); +} diff --git a/gcc/flow.c b/gcc/flow.c index 688e256c339..3b5539e8319 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -136,6 +136,7 @@ Boston, MA 02111-1307, USA. */ #include "recog.h" #include "insn-flags.h" #include "expr.h" +#include "ssa.h" #include "obstack.h" #include "splay-tree.h" @@ -308,6 +309,20 @@ struct propagate_block_info int flags; }; +/* Store the data structures necessary for depth-first search. */ +struct depth_first_search_dsS { + /* stack for backtracking during the algorithm */ + basic_block *stack; + + /* number of edges in the stack. That is, positions 0, ..., sp-1 + have edges. */ + unsigned int sp; + + /* record of basic blocks already seen by depth-first search */ + sbitmap visited_blocks; +}; +typedef struct depth_first_search_dsS *depth_first_search_ds; + /* Forward declarations */ static int count_basic_blocks PARAMS ((rtx)); static void find_basic_blocks_1 PARAMS ((rtx)); @@ -398,6 +413,14 @@ static int flow_loop_nested_p PARAMS ((struct loop *, struct loop *)); static int flow_loop_exits_find PARAMS ((const sbitmap, edge **)); static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap)); static int flow_depth_first_order_compute PARAMS ((int *, int *)); +static void flow_dfs_compute_reverse_init + PARAMS ((depth_first_search_ds)); +static void flow_dfs_compute_reverse_add_bb + PARAMS ((depth_first_search_ds, basic_block)); +static basic_block flow_dfs_compute_reverse_execute + PARAMS ((depth_first_search_ds)); +static void flow_dfs_compute_reverse_finish + PARAMS ((depth_first_search_ds)); static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *)); static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *)); static void flow_loops_tree_build PARAMS ((struct loops *)); @@ -3741,7 +3764,7 @@ init_propagate_block_info (bb, live, local_set, flags) && GET_CODE (SET_DEST (PATTERN (insn))) == MEM) { rtx mem = SET_DEST (PATTERN (insn)); - + if (XEXP (mem, 0) == frame_pointer_rtx || (GET_CODE (XEXP (mem, 0)) == PLUS && XEXP (XEXP (mem, 0), 0) == frame_pointer_rtx @@ -6254,7 +6277,6 @@ compute_immediate_postdominators (idom, postdominators) sbitmap *postdominators; { compute_immediate_dominators (idom, postdominators); - return; } /* Recompute register set/reference counts immediately prior to register @@ -6888,7 +6910,6 @@ verify_edge_list (f, elist) /* This routine will determine what, if any, edge there is between a specified predecessor and successor. */ - int find_edge_index (edge_list, pred, succ) struct edge_list *edge_list; @@ -6984,8 +7005,44 @@ add_noreturn_fake_exit_edges () make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE); } -/* Redirect an edge's successor from one block to another. */ +/* This function adds a fake edge between any infinite loops to the + exit block. Some optimizations require a path from each node to + the exit node. + See also Morgan, Figure 3.10, pp. 82-83. + + The current implementation is ugly, not attempting to minimize the + number of inserted fake edges. To reduce the number of fake edges + to insert, add fake edges from _innermost_ loops containing only + nodes not reachable from the exit block. */ +void +connect_infinite_loops_to_exit () +{ + basic_block unvisited_block; + + /* Perform depth-first search in the reverse graph to find nodes + reachable from the exit block. */ + struct depth_first_search_dsS dfs_ds; + + flow_dfs_compute_reverse_init (&dfs_ds); + flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR); + + /* Repeatedly add fake edges, updating the unreachable nodes. */ + while (1) + { + unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds); + if (!unvisited_block) + break; + make_edge (NULL, unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE); + flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block); + } + + flow_dfs_compute_reverse_finish (&dfs_ds); + + return; +} + +/* Redirect an edge's successor from one block to another. */ void redirect_edge_succ (e, new_succ) edge e; @@ -7005,7 +7062,6 @@ redirect_edge_succ (e, new_succ) } /* Redirect an edge's predecessor from one block to another. */ - void redirect_edge_pred (e, new_pred) edge e; @@ -7427,6 +7483,115 @@ flow_depth_first_order_compute (dfs_order, rc_order) } +/* Compute the depth first search order on the _reverse_ graph and + store in the array DFS_ORDER, marking the nodes visited in VISITED. + Returns the number of nodes visited. + + The computation is split into three pieces: + + flow_dfs_compute_reverse_init () creates the necessary data + structures. + + flow_dfs_compute_reverse_add_bb () adds a basic block to the data + structures. The block will start the search. + + flow_dfs_compute_reverse_execute () continues (or starts) the + search using the block on the top of the stack, stopping when the + stack is empty. + + flow_dfs_compute_reverse_finish () destroys the necessary data + structures. + + Thus, the user will probably call ..._init(), call ..._add_bb() to + add a beginning basic block to the stack, call ..._execute(), + possibly add another bb to the stack and again call ..._execute(), + ..., and finally call _finish(). */ + +/* Initialize the data structures used for depth-first search on the + reverse graph. If INITIALIZE_STACK is nonzero, the exit block is + added to the basic block stack. DATA is the current depth-first + search context. If INITIALIZE_STACK is non-zero, there is an + element on the stack. */ + +static void +flow_dfs_compute_reverse_init (data) + depth_first_search_ds data; +{ + /* Allocate stack for back-tracking up CFG. */ + data->stack = + (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK+1)) + * sizeof (basic_block)); + data->sp = 0; + + /* Allocate bitmap to track nodes that have been visited. */ + data->visited_blocks + = sbitmap_alloc (n_basic_blocks - (INVALID_BLOCK + 1)); + + /* None of the nodes in the CFG have been visited yet. */ + sbitmap_zero (data->visited_blocks); + + return; +} + +/* Add the specified basic block to the top of the dfs data + structures. When the search continues, it will start at the + block. */ + +static void +flow_dfs_compute_reverse_add_bb (data, bb) + depth_first_search_ds data; + basic_block bb; +{ + data->stack[data->sp++] = bb; + return; +} + +/* Continue the depth-first search through the reverse graph starting + with the block at the stack's top and ending when the stack is + empty. Visited nodes are marked. Returns an unvisited basic + block, or NULL if there is none available. */ +static basic_block +flow_dfs_compute_reverse_execute (data) + depth_first_search_ds data; +{ + basic_block bb; + edge e; + int i; + + while (data->sp > 0) + { + bb = data->stack[--data->sp]; + + /* Mark that we have visited this node. */ + if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK+1))) + { + SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK+1)); + + /* Perform depth-first search on adjacent vertices. */ + for (e = bb->pred; e; e = e->pred_next) + flow_dfs_compute_reverse_add_bb (data, e->src); + } + } + + /* Determine if there are unvisited basic blocks. */ + for (i = n_basic_blocks - (INVALID_BLOCK+1); --i >= 0; ) + if (!TEST_BIT (data->visited_blocks, i)) + return BASIC_BLOCK (i + (INVALID_BLOCK+1)); + return NULL; +} + +/* Destroy the data structures needed for depth-first search on the + reverse graph. */ + +static void +flow_dfs_compute_reverse_finish (data) + depth_first_search_ds data; +{ + free (data->stack); + sbitmap_free (data->visited_blocks); + return; +} + /* Return the block for the pre-header of the loop with header HEADER where DOM specifies the dominator information. Return NULL if there is no pre-header. */ diff --git a/gcc/invoke.texi b/gcc/invoke.texi index 382fb7bb773..912428ba9ee 100644 --- a/gcc/invoke.texi +++ b/gcc/invoke.texi @@ -168,7 +168,7 @@ in the following sections. -falign-functions=@var{n} -falign-labels=@var{n} -falign-loops=@var{n} -falign-jumps=@var{n} -fbranch-probabilities -fcaller-saves -fcse-follow-jumps -fcse-skip-blocks --fdelayed-branch -fdelete-null-pointer-checks -fexpensive-optimizations +-fdce -fdelayed-branch -fdelete-null-pointer-checks -fexpensive-optimizations -ffast-math -ffloat-store -fforce-addr -fforce-mem -fno-math-errno -fdata-sections -ffunction-sections -fgcse -finline-functions -finline-limit=@var{n} -fkeep-inline-functions @@ -2900,9 +2900,12 @@ If @var{n} is not specified, use a machine-dependent default. @item -fssa Perform optimizations in static single assignment form. Each function's flow graph is translated into SSA form, optimizations are performed, and -the flow graph is translated back from SSA form. (Currently, no -SSA-based optimizations are implemented, but converting into and out of -SSA form is not an invariant operation, and generated code may differ.) +the flow graph is translated back from SSA form. User's should not +specify this option, since it is not yet ready for production use. + +@item -fdce +Perform dead-code elimination in SSA form. Requires @samp{-fssa}. Like +@samp{-fssa}, this is an experimental feature. @item -fsingle-precision-constant Treat floating point constant as single precision constant instead of diff --git a/gcc/rtl.h b/gcc/rtl.h index b96c53f3267..41caa802be6 100644 --- a/gcc/rtl.h +++ b/gcc/rtl.h @@ -148,7 +148,9 @@ typedef struct rtx_def together with the preceding insn. Valid only within sched. 1 in an INSN, JUMP_INSN, or CALL_INSN if insn is in a delay slot and from the target of a branch. Valid from reorg until end of compilation; - cleared before used. */ + cleared before used. + 1 in an INSN if this insn is dead code. Valid only during + dead-code elimination phase; cleared before use. */ unsigned int in_struct : 1; /* 1 if this rtx is used. This is used for copying shared structure. See `unshare_all_rtl'. @@ -202,10 +204,26 @@ typedef struct rtvec_def{ #define GET_NUM_ELEM(RTVEC) ((RTVEC)->num_elem) #define PUT_NUM_ELEM(RTVEC, NUM) ((RTVEC)->num_elem = (NUM)) -/* 1 if X is a REG. */ - +/* Predicate yielding nonzero iff X is an rtl for a register. */ #define REG_P(X) (GET_CODE (X) == REG) +/* Predicate yielding nonzero iff X is a label insn. */ +#define LABEL_P(X) (GET_CODE (X) == CODE_LABEL) + +/* Predicate yielding nonzero iff X is a jump insn. */ +#define JUMP_P(X) (GET_CODE (X) == JUMP_INSN) + +/* Predicate yielding nonzero iff X is a note insn. */ +#define NOTE_P(X) (GET_CODE (X) == NOTE) + +/* Predicate yielding nonzero iff X is a barrier insn. */ +#define BARRIER_P(X) (GET_CODE (X) == BARRIER) + +/* Predicate yielding nonzero iff X is a data for a jump table. */ +#define JUMP_TABLE_DATA_P(INSN) \ + (JUMP_P (INSN) && (GET_CODE (PATTERN (INSN)) == ADDR_VEC || \ + GET_CODE (PATTERN (INSN)) == ADDR_DIFF_VEC)) + /* 1 if X is a constant value that is an integer. */ #define CONSTANT_P(X) \ @@ -374,6 +392,9 @@ extern void rtvec_check_failed_bounds PARAMS ((rtvec, int, delay slots, i.e., it is an annulled branch. */ #define INSN_ANNULLED_BRANCH_P(INSN) ((INSN)->unchanging) +/* 1 if insn is a dead code. Valid only for dead-code elimination phase. */ +#define INSN_DEAD_CODE_P(INSN) ((INSN)->in_struct) + /* 1 if insn is in a delay slot and is from the target of the branch. If the branch insn has INSN_ANNULLED_BRANCH_P set, this insn should only be executed if the branch is taken. For annulled branches with this bit diff --git a/gcc/ssa.c b/gcc/ssa.c index 61ce4ced7e8..bb4bda71aab 100644 --- a/gcc/ssa.c +++ b/gcc/ssa.c @@ -46,6 +46,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "recog.h" #include "basic-block.h" #include "output.h" +#include "ssa.h" /* We cannot use <assert.h> in GCC source, since that would include GCC's assert.h, which may not be compatible with the host compiler. */ @@ -91,24 +92,6 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA left in for a limited time only, as a debugging tool until the coalescing algorithm is validated. */ -/* All pseudo-registers (having register number >= - FIRST_PSEUDO_REGISTER) and hard registers satisfying - CONVERT_HARD_REGISTER_TO_SSA_P are converted to SSA form. */ - -/* Given a hard register number REG_NO, return nonzero if and only if - the register should be converted to SSA. */ - -#ifndef CONVERT_HARD_REGISTER_TO_SSA_P -#define CONVERT_HARD_REGISTER_TO_SSA_P(REG_NO) (0) /* default of no hard registers */ -#endif /* CONVERT_HARD_REGISTER_TO_SSA_P */ - -/* Given a register number REG_NO, return nonzero if and only if the - register should be converted to SSA. */ - -#define CONVERT_REGISTER_TO_SSA_P(REG_NO) \ - ((!HARD_REGISTER_NUM_P (REG_NO)) || \ - (CONVERT_HARD_REGISTER_TO_SSA_P (REG_NO))) - static int conservative_reg_partition; /* This flag is set when the CFG is in SSA form. */ @@ -152,20 +135,20 @@ struct ssa_rename_from_hash_table_data { partition reg_partition; }; -void ssa_rename_from_initialize +static void ssa_rename_from_initialize PARAMS ((void)); -rtx ssa_rename_from_lookup +static rtx ssa_rename_from_lookup PARAMS ((int reg)); -unsigned int original_register +static unsigned int original_register PARAMS ((unsigned int regno)); -void ssa_rename_from_insert +static void ssa_rename_from_insert PARAMS ((unsigned int reg, rtx r)); -void ssa_rename_from_free +static void ssa_rename_from_free PARAMS ((void)); typedef int (*srf_trav) PARAMS ((int regno, rtx r, sbitmap canonical_elements, partition reg_partition)); static void ssa_rename_from_traverse PARAMS ((htab_trav callback_function, sbitmap canonical_elements, partition reg_partition)); -static void ssa_rename_from_print +/*static Avoid warnign message. */ void ssa_rename_from_print PARAMS ((void)); static int ssa_rename_from_print_1 PARAMS ((void **slot, void *data)); @@ -299,7 +282,7 @@ ssa_rename_to_insert(reg, r) /* Prepare ssa_rename_from for use. */ -void +static void ssa_rename_from_initialize () { /* We use an arbitrary initial hash table size of 64. */ @@ -312,7 +295,7 @@ ssa_rename_from_initialize () /* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is found. */ -rtx +static rtx ssa_rename_from_lookup (reg) int reg; { @@ -329,7 +312,7 @@ ssa_rename_from_lookup (reg) the register is a pseudo, return the original register's number. Otherwise, return this register number REGNO. */ -unsigned int +static unsigned int original_register (regno) unsigned int regno; { @@ -339,7 +322,7 @@ original_register (regno) /* Add mapping from R to REG to ssa_rename_from even if already present. */ -void +static void ssa_rename_from_insert (reg, r) unsigned int reg; rtx r; @@ -359,7 +342,7 @@ ssa_rename_from_insert (reg, r) CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only current use of this function. */ -void +static void ssa_rename_from_traverse (callback_function, canonical_elements, reg_partition) htab_trav callback_function; @@ -374,7 +357,7 @@ ssa_rename_from_traverse (callback_function, /* Destroy ssa_rename_from. */ -void +static void ssa_rename_from_free () { htab_delete (ssa_rename_from_ht); @@ -382,7 +365,8 @@ ssa_rename_from_free () /* Print the contents of ssa_rename_from. */ -static void +/* static Avoid erroneous error message. */ +void ssa_rename_from_print () { printf ("ssa_rename_from's hash table contents:\n"); @@ -1146,9 +1130,6 @@ rename_registers (nregs, idom) int nregs; int *idom; { - int reg; - int mach_mode; - VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition"); VARRAY_RTX_INIT (ssa_uses, nregs * 3, "ssa_uses"); ssa_rename_from_initialize (); diff --git a/gcc/ssa.h b/gcc/ssa.h new file mode 100644 index 00000000000..463fef8b60c --- /dev/null +++ b/gcc/ssa.h @@ -0,0 +1,64 @@ +/* Static Single Assignment (SSA) definitions for GNU C-Compiler + Copyright (C) 2000 Free Software Foundation, Inc. + Written by Jeffrey D. Oldham <oldham@codesourcery.com>. + +This file is part of GNU CC. + +GNU CC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU CC; see the file COPYING. If not, write to +the Free Software Foundation, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + + +/* Main SSA routines. */ +extern void convert_to_ssa PARAMS ((void)); +extern void convert_from_ssa PARAMS ((void)); +typedef int (*successor_phi_fn) PARAMS ((rtx, int, int, void *)); +extern int for_each_successor_phi PARAMS ((basic_block bb, + successor_phi_fn, + void *)); + +/* Optimizations. */ +/* In dce.c */ +extern void eliminate_dead_code PARAMS ((void)); + +/* SSA definitions and uses. */ +/* This flag is set when the CFG is in SSA form. */ +extern int in_ssa_form; + +/* Element I is the single instruction that sets register I. */ +extern varray_type ssa_definition; + +/* Element I is an INSN_LIST of instructions that use register I. */ +extern varray_type ssa_uses; + + +/* Specify which hard registers should be converted. */ + +/* All pseudo-registers (having register number >= + FIRST_PSEUDO_REGISTER) and hard registers satisfying + CONVERT_HARD_REGISTER_TO_SSA_P are converted to SSA form. */ + +/* Given a hard register number REG_NO, return nonzero if and only if + the register should be converted to SSA. */ + +#ifndef CONVERT_HARD_REGISTER_TO_SSA_P +#define CONVERT_HARD_REGISTER_TO_SSA_P(REG_NO) (0) /* default of no hard registers */ +#endif /* CONVERT_HARD_REGISTER_TO_SSA_P */ + +/* Given a register number REG_NO, return nonzero if and only if the + register should be converted to SSA. */ + +#define CONVERT_REGISTER_TO_SSA_P(REG_NO) \ + ((!HARD_REGISTER_NUM_P (REG_NO)) || \ + (CONVERT_HARD_REGISTER_TO_SSA_P (REG_NO))) diff --git a/gcc/timevar.def b/gcc/timevar.def index 2f3458a9111..19a3bb26e3b 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -68,6 +68,7 @@ DEFTIMEVAR (TV_REORDER_BLOCKS , "reorder blocks") DEFTIMEVAR (TV_SHORTEN_BRANCH , "shorten branches") DEFTIMEVAR (TV_REG_STACK , "reg stack") DEFTIMEVAR (TV_TO_SSA , "convert to SSA") +DEFTIMEVAR (TV_DEAD_CODE_ELIM , "eliminate dead code") DEFTIMEVAR (TV_FROM_SSA , "convert from SSA") DEFTIMEVAR (TV_FINAL , "final") DEFTIMEVAR (TV_SYMOUT , "symout") diff --git a/gcc/toplev.c b/gcc/toplev.c index fde14d16b5f..b13e580ce59 100644 --- a/gcc/toplev.c +++ b/gcc/toplev.c @@ -63,6 +63,7 @@ Boston, MA 02111-1307, USA. */ #include "regs.h" #include "timevar.h" #include "diagnostic.h" +#include "ssa.h" #ifndef ACCUMULATE_OUTGOING_ARGS #define ACCUMULATE_OUTGOING_ARGS 0 @@ -259,6 +260,7 @@ enum dump_file_index DFI_cse, DFI_addressof, DFI_ssa, + DFI_dce, DFI_ussa, DFI_gcse, DFI_loop, @@ -291,7 +293,7 @@ enum dump_file_index Remaining -d letters: " h o q u " - " H K OPQ TUVWXYZ" + " H K OPQ TUVW YZ" */ struct dump_file_info dump_file[DFI_MAX] = @@ -302,6 +304,7 @@ struct dump_file_info dump_file[DFI_MAX] = { "cse", 's', 0, 0, 0 }, { "addressof", 'F', 0, 0, 0 }, { "ssa", 'e', 1, 0, 0 }, + { "dce", 'X', 1, 0, 0 }, { "ussa", 'e', 1, 0, 0 }, /* Yes, duplicate enable switch. */ { "gcse", 'G', 1, 0, 0 }, { "loop", 'L', 1, 0, 0 }, @@ -786,6 +789,9 @@ int flag_gnu_linker = 1; /* Enable SSA. */ int flag_ssa = 0; +/* Enable dead code elimination. */ +int flag_dce = 0; + /* Tag all structures with __attribute__(packed) */ int flag_pack_struct = 0; @@ -1094,6 +1100,8 @@ lang_independent_options f_options[] = "Instrument function entry/exit with profiling calls"}, {"ssa", &flag_ssa, 1, "Enable SSA optimizations" }, + {"dce", &flag_dce, 1, + "Enable dead code elimination" }, {"leading-underscore", &flag_leading_underscore, 1, "External symbols have a leading underscore" }, {"ident", &flag_no_ident, 0, @@ -2976,13 +2984,25 @@ rest_of_compilation (decl) close_dump_file (DFI_ssa, print_rtl_with_bb, insns); timevar_pop (TV_TO_SSA); - /* Currently, there's nothing to do in SSA form. */ - /* The SSA implementation uses basic block numbers in its phi nodes. Thus, changing the control-flow graph or the basic blocks, e.g., calling find_basic_blocks () or cleanup_cfg (), may cause problems. */ + if (flag_dce) + { + /* Remove dead code. */ + + timevar_push (TV_DEAD_CODE_ELIM); + open_dump_file (DFI_dce, decl); + + insns = get_insns (); + eliminate_dead_code(); + + close_dump_file (DFI_dce, print_rtl_with_bb, insns); + timevar_pop (TV_DEAD_CODE_ELIM); + } + /* Convert from SSA form. */ timevar_push (TV_FROM_SSA); |