/* Conditional constant propagation pass for the GNU compiler. Copyright (C) 2000,2001 Free Software Foundation, Inc. Original framework by Daniel Berlin Fleshed out and major cleanups by Jeff Law 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. */ /* Conditional constant propagation. References: Constant propagation with conditional branches, Wegman and Zadeck, ACM TOPLAS 13(2):181-210. Building an Optimizing Compiler, Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. Advanced Compiler Design and Implementation, Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 The overall structure is as follows: 1. Run a simple SSA based DCE pass to remove any dead code. 2. Run CCP to compute what registers are known constants and what edges are not executable. Remove unexecutable edges from the CFG and simplify PHI nodes. 3. Replace registers with constants where possible. 4. Remove unreachable blocks computed in step #2. 5. Another simple SSA DCE pass to remove dead code exposed by CCP. When we exit, we are still in SSA form. Potential further enhancements: 1. Handle SUBREGs, STRICT_LOW_PART, etc in destinations more gracefully. 2. Handle insns with multiple outputs more gracefully. 3. Handle CONST_DOUBLE and symbolic constants. 4. Fold expressions after performing constant substitutions. */ #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" #include "errors.h" #include "ggc.h" #include "df.h" #include "function.h" /* Possible lattice values. */ typedef enum { UNDEFINED, CONSTANT, VARYING } latticevalue; /* Main structure for CCP. Contains the lattice value and, if it's a constant, the constant value. */ typedef struct { latticevalue lattice_val; rtx const_value; } value; /* Array of values indexed by register number. */ static value *values; /* A bitmap to keep track of executable blocks in the CFG. */ static sbitmap executable_blocks; /* A bitmap for all executable edges in the CFG. */ static sbitmap executable_edges; /* Array of edges on the work list. */ static edge *edge_info; /* We need an edge list to be able to get indexes easily. */ static struct edge_list *edges; /* For building/following use-def and def-use chains. */ static struct df *df_analyzer; /* Current edge we are operating on, from the worklist */ static edge flow_edges; /* Bitmap of SSA edges which will need reexamination as their definition has changed. */ static sbitmap ssa_edges; /* Simple macros to simplify code */ #define SSA_NAME(x) REGNO (SET_DEST (x)) #define PHI_PARMS(x) XVEC (SET_SRC (x), 0) #define EIE(x,y) EDGE_INDEX (edges, x, y) static void visit_phi_node PARAMS ((rtx, basic_block)); static void visit_expression PARAMS ((rtx, basic_block)); static void defs_to_undefined PARAMS ((rtx)); static void defs_to_varying PARAMS ((rtx)); static void examine_flow_edges PARAMS ((void)); static int mark_references PARAMS ((rtx *, void *)); static void follow_def_use_chains PARAMS ((void)); static void optimize_unexecutable_edges PARAMS ((struct edge_list *, sbitmap)); static void ssa_ccp_substitute_constants PARAMS ((void)); static void ssa_ccp_df_delete_unreachable_insns PARAMS ((void)); static void ssa_fast_dce PARAMS ((struct df *)); /* Loop through the PHI_NODE's parameters for BLOCK and compare their lattice values to determine PHI_NODE's lattice value. */ static void visit_phi_node (phi_node, block) rtx phi_node; basic_block block; { unsigned int i; rtx phi_node_expr = NULL; unsigned int phi_node_name = SSA_NAME (PATTERN (phi_node)); latticevalue phi_node_lattice_val = UNDEFINED; rtx pat = PATTERN (phi_node); rtvec phi_vec = XVEC (SET_SRC (pat), 0); unsigned int num_elem = GET_NUM_ELEM (phi_vec); for (i = 0; i < num_elem; i += 2) { if (TEST_BIT (executable_edges, EIE (BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, i + 1))), block))) { unsigned int current_parm = REGNO (RTVEC_ELT (phi_vec, i)); latticevalue current_parm_lattice_val = values[current_parm].lattice_val; /* If any node is VARYING, then new value of PHI_NODE is VARYING. */ if (current_parm_lattice_val == VARYING) { phi_node_lattice_val = VARYING; phi_node_expr = NULL; break; } /* If we have more than one distinct constant, then the new value of PHI_NODE is VARYING. */ if (current_parm_lattice_val == CONSTANT && phi_node_lattice_val == CONSTANT && values[current_parm].const_value != phi_node_expr) { phi_node_lattice_val = VARYING; phi_node_expr = NULL; break; } /* If the current value of PHI_NODE is UNDEFINED and one node in PHI_NODE is CONSTANT, then the new value of the PHI is that CONSTANT. Note this can turn into VARYING if we find another distinct constant later. */ if (phi_node_lattice_val == UNDEFINED && phi_node_expr == NULL && current_parm_lattice_val == CONSTANT) { phi_node_expr = values[current_parm].const_value; phi_node_lattice_val = CONSTANT; continue; } } } /* If the value of PHI_NODE changed, then we will need to re-execute uses of the output of PHI_NODE. */ if (phi_node_lattice_val != values[phi_node_name].lattice_val) { values[phi_node_name].lattice_val = phi_node_lattice_val; values[phi_node_name].const_value = phi_node_expr; SET_BIT (ssa_edges, phi_node_name); } } /* Sets all defs in an insn to UNDEFINED. */ static void defs_to_undefined (insn) rtx insn; { struct df_link *currdef; for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef; currdef = currdef->next) { if (values[DF_REF_REGNO (currdef->ref)].lattice_val != UNDEFINED) SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref)); values[DF_REF_REGNO (currdef->ref)].lattice_val = UNDEFINED; } } /* Sets all defs in an insn to VARYING. */ static void defs_to_varying (insn) rtx insn; { struct df_link *currdef; for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef; currdef = currdef->next) { if (values[DF_REF_REGNO (currdef->ref)].lattice_val != VARYING) SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref)); values[DF_REF_REGNO (currdef->ref)].lattice_val = VARYING; } } /* Go through the expression, call the approriate evaluation routines to attempt cprop */ static void visit_expression (insn, block) rtx insn; basic_block block; { rtx src, dest, set; set = single_set (insn); if (! set) { defs_to_varying (insn); return; } src = SET_SRC (set); dest = SET_DEST (set); /* We may want to refine this some day. */ if (GET_CODE (dest) != REG && dest != pc_rtx) { defs_to_varying (insn); return; } /* Hard registers are not put in SSA form and thus we must consider them varying. All the more reason to avoid hard registers in RTL until as late as possible in the compilation. */ if (GET_CODE (dest) == REG && REGNO (dest) < FIRST_PSEUDO_REGISTER) { defs_to_varying (insn); return; } /* If this is assigning DEST to a constant, record that fact. */ if (GET_CODE (src) == CONST_INT && GET_CODE (insn) == INSN) { unsigned int resultreg = REGNO (dest); values[resultreg].lattice_val = CONSTANT; values[resultreg].const_value = SET_SRC (PATTERN (insn)); SET_BIT (ssa_edges, resultreg); } /* If this is a copy operation, then we can copy the lattice values. */ else if (GET_CODE (src) == REG && GET_CODE (dest) == REG) { unsigned int old_value = REGNO (src); latticevalue old_lattice_value = values[old_value].lattice_val; unsigned int new_value = REGNO (dest); /* Unless the lattice value is going to change, don't bother adding the "new value" into the worklist. */ if (values[new_value].lattice_val != old_lattice_value || values[new_value].const_value != values[old_value].const_value) SET_BIT (ssa_edges, new_value); /* Copy the old lattice node info into the new value lattice node. */ values[new_value].lattice_val = old_lattice_value; values[new_value].const_value = values[old_value].const_value; } /* Handle jumps. */ else if (GET_CODE (insn) == JUMP_INSN) { rtx x = pc_set (insn); if (GET_CODE (src) != IF_THEN_ELSE) { edge curredge; /* This is a computed jump, table jump, or an unconditional jump. For all these cases we want to mark all successor blocks as executable if they have not already been marked. One day we may try do better with swtich tables and other computed jumps. */ for (curredge = block->succ; curredge; curredge = curredge->succ_next) { int index = EIE (curredge->src, curredge->dest); if (TEST_BIT (executable_edges, index)) continue; SET_BIT (executable_edges, index); edge_info[index] = flow_edges; flow_edges = curredge; } } else { edge curredge; enum rtx_code comparison_code; rtx comparison_src0; rtx comparison_src1; comparison_code = GET_CODE (XEXP (src, 0)); comparison_src0 = XEXP (XEXP (src, 0), 0); comparison_src1 = XEXP (XEXP (src, 0), 1); /* If either operand is undefined, then there is nothing to do right now. If/when operands are later defined we will revaluate the condition and take the appropriate action. */ if ((GET_CODE (comparison_src0) == REG && values[REGNO (comparison_src0)].lattice_val == UNDEFINED) || (GET_CODE (comparison_src1) == REG && values[REGNO (comparison_src1)].lattice_val == UNDEFINED)) return; /* If either operand is varying, then we must consider all paths as executable. */ if ((GET_CODE (comparison_src0) == REG && values[REGNO (comparison_src0)].lattice_val == VARYING) || (GET_CODE (comparison_src1) == REG && values[REGNO (comparison_src1)].lattice_val == VARYING)) { for (curredge = block->succ; curredge; curredge = curredge->succ_next) { int index = EIE (curredge->src, curredge->dest); if (TEST_BIT (executable_edges, index)) continue; SET_BIT (executable_edges, index); edge_info[index] = flow_edges; flow_edges = curredge; } return; } /* Try to simplify the comparison. */ if (GET_CODE (comparison_src0) == REG && values[REGNO (comparison_src0)].lattice_val == CONSTANT) comparison_src0 = values[REGNO (comparison_src0)].const_value; if (GET_CODE (comparison_src1) == REG && values[REGNO (comparison_src1)].lattice_val == CONSTANT) comparison_src1 = values[REGNO (comparison_src1)].const_value; x = simplify_ternary_operation (IF_THEN_ELSE, VOIDmode, GET_MODE (XEXP (src, 0)), gen_rtx (comparison_code, GET_MODE (XEXP (src, 0)), comparison_src0, comparison_src1), XEXP (src, 1), XEXP (src, 2)); /* Walk through all the outgoing edges from this block and see which (if any) we should mark as executable. */ for (curredge = block->succ; curredge; curredge = curredge->succ_next) { int index = EIE (curredge->src, curredge->dest); if (TEST_BIT (executable_edges, index)) continue; /* If we were unable to simplify the expression at this point, it's highly unlikely we'll be able to simplify it later. So consider all edges as executable if the expression did not simplify. If the expression simplified to (pc), then we know we will take the fall-thru edge, so mark it. Similarly, if the expression simplified to (label_ref ...), then we know the branch will be taken and we mark that edge as taken. */ if (!x || (x == pc_rtx && (curredge->flags & EDGE_FALLTHRU)) || (GET_CODE (x) == LABEL_REF && ! (curredge->flags & EDGE_FALLTHRU))) { SET_BIT (executable_edges, index); edge_info[index] = flow_edges; flow_edges = curredge; } } } } else if (!PHI_NODE_P (insn)) { rtx simplified = NULL; /* We've got some kind of INSN. If it's simple, try to evaluate it and record the results. We already know this insn is a single_set and that it sets a pseudo register. So we just need to extract the source arguments, simplify them to constants if possible, then simplify the expression as a whole if possible. */ switch (GET_RTX_CLASS (GET_CODE (src))) { case '<': { rtx src0 = XEXP (src, 0); rtx src1 = XEXP (src, 1); enum machine_mode mode; /* If either is undefined, then the result is undefined. */ if ((GET_CODE (src0) == REG && values[REGNO (src0)].lattice_val == UNDEFINED) || (GET_CODE (src1) == REG && values[REGNO (src1)].lattice_val == UNDEFINED)) { defs_to_undefined (insn); break; } /* Simplify source operands to whatever known values they may have. */ if (GET_CODE (src0) == REG && values[REGNO (src0)].lattice_val == CONSTANT) src0 = values[REGNO (src0)].const_value; if (GET_CODE (src1) == REG && values[REGNO (src1)].lattice_val == CONSTANT) src1 = values[REGNO (src1)].const_value; /* See if the simplifier can determine if this operation computes a constant value. */ mode = GET_MODE (src0); if (mode == VOIDmode) mode = GET_MODE (src1); simplified = simplify_relational_operation (GET_CODE (src), mode, src0, src1); break; } case '1': { rtx src0 = XEXP (src, 0); /* If the operand is undefined, then the result is undefined. */ if (GET_CODE (src0) == REG && values[REGNO (src0)].lattice_val == UNDEFINED) { defs_to_undefined (insn); break; } /* Simplify source operands to whatever known values they may have. */ if (GET_CODE (src0) == REG && values[REGNO (src0)].lattice_val == CONSTANT) src0 = values[REGNO (src0)].const_value; /* See if the simplifier can determine if this operation computes a constant value. */ simplified = simplify_unary_operation (GET_CODE (src), GET_MODE (src), src0, GET_MODE (src0)); break; } case '2': case 'c': { rtx src0 = XEXP (src, 0); rtx src1 = XEXP (src, 1); /* If either is undefined, then the result is undefined. */ if ((GET_CODE (src0) == REG && values[REGNO (src0)].lattice_val == UNDEFINED) || (GET_CODE (src1) == REG && values[REGNO (src1)].lattice_val == UNDEFINED)) { defs_to_undefined (insn); break; } /* Simplify source operands to whatever known values they may have. */ if (GET_CODE (src0) == REG && values[REGNO (src0)].lattice_val == CONSTANT) src0 = values[REGNO (src0)].const_value; if (GET_CODE (src1) == REG && values[REGNO (src1)].lattice_val == CONSTANT) src1 = values[REGNO (src1)].const_value; /* See if the simplifier can determine if this operation computes a constant value. */ simplified = simplify_binary_operation (GET_CODE (src), GET_MODE (src), src0, src1); break; } case '3': case 'b': { rtx src0 = XEXP (src, 0); rtx src1 = XEXP (src, 1); rtx src2 = XEXP (src, 2); /* If either is undefined, then the result is undefined. */ if ((GET_CODE (src0) == REG && values[REGNO (src0)].lattice_val == UNDEFINED) || (GET_CODE (src1) == REG && values[REGNO (src1)].lattice_val == UNDEFINED) || (GET_CODE (src2) == REG && values[REGNO (src2)].lattice_val == UNDEFINED)) { defs_to_undefined (insn); break; } /* Simplify source operands to whatever known values they may have. */ if (GET_CODE (src0) == REG && values[REGNO (src0)].lattice_val == CONSTANT) src0 = values[REGNO (src0)].const_value; if (GET_CODE (src1) == REG && values[REGNO (src1)].lattice_val == CONSTANT) src1 = values[REGNO (src1)].const_value; if (GET_CODE (src2) == REG && values[REGNO (src2)].lattice_val == CONSTANT) src2 = values[REGNO (src2)].const_value; /* See if the simplifier can determine if this operation computes a constant value. */ simplified = simplify_ternary_operation (GET_CODE (src), GET_MODE (src), GET_MODE (src), src0, src1, src2); break; } default: defs_to_varying (insn); } if (simplified && GET_CODE (simplified) == CONST_INT) { if (values[REGNO (dest)].lattice_val != CONSTANT || values[REGNO (dest)].const_value != simplified) SET_BIT (ssa_edges, REGNO (dest)); values[REGNO (dest)].lattice_val = CONSTANT; values[REGNO (dest)].const_value = simplified; } else defs_to_varying (insn); } } /* Iterate over the FLOW_EDGES work list. Simulate the target block for each edge. */ static void examine_flow_edges (void) { while (flow_edges != NULL) { basic_block succ_block; rtx curr_phi_node; /* Pull the next block to simulate off the worklist. */ succ_block = flow_edges->dest; flow_edges = edge_info[EIE (flow_edges->src, flow_edges->dest)]; /* There is nothing to do for the exit block. */ if (succ_block == EXIT_BLOCK_PTR) continue; /* Always simulate PHI nodes, even if we have simulated this block before. Note that all PHI nodes are consecutive within a block. */ for (curr_phi_node = first_insn_after_basic_block_note (succ_block); PHI_NODE_P (curr_phi_node); curr_phi_node = NEXT_INSN (curr_phi_node)) visit_phi_node (curr_phi_node, succ_block); /* If this is the first time we've simulated this block, then we must simulate each of its insns. */ if (!TEST_BIT (executable_blocks, succ_block->index)) { rtx currinsn; edge succ_edge = succ_block->succ; /* Note that we have simulated this block. */ SET_BIT (executable_blocks, succ_block->index); /* Simulate each insn within the block. */ currinsn = succ_block->head; while (currinsn != succ_block->end) { if (INSN_P (currinsn)) visit_expression (currinsn, succ_block); currinsn = NEXT_INSN (currinsn); } /* Don't forget the last insn in the block. */ if (INSN_P (currinsn)) visit_expression (currinsn, succ_block); /* If we haven't looked at the next block, and it has a single successor, add it onto the worklist. This is because if we only have one successor, we know it gets executed, so we don't have to wait for cprop to tell us. */ if (succ_edge != NULL && succ_edge->succ_next == NULL && !TEST_BIT (executable_edges, EIE (succ_edge->src, succ_edge->dest))) { SET_BIT (executable_edges, EIE (succ_edge->src, succ_edge->dest)); edge_info[EIE (succ_edge->src, succ_edge->dest)] = flow_edges; flow_edges = succ_edge; } } } } /* Follow the def-use chains for each definition on the worklist and simulate the uses of the definition. */ static void follow_def_use_chains () { /* Iterate over all the entries on the SSA_EDGES worklist. */ while (sbitmap_first_set_bit (ssa_edges) >= 0) { int member; struct df_link *curruse; /* Pick an entry off the worklist (it does not matter which entry we pick). */ member = sbitmap_first_set_bit (ssa_edges); RESET_BIT (ssa_edges, member); /* Iterate through all the uses of this entry. */ for (curruse = df_analyzer->regs[member].uses; curruse; curruse = curruse->next) { rtx useinsn; useinsn = DF_REF_INSN (curruse->ref); if (PHI_NODE_P (useinsn)) { if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn))) visit_phi_node (useinsn, BLOCK_FOR_INSN (useinsn)); } else { if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn))) visit_expression (useinsn, BLOCK_FOR_INSN (useinsn)); } } } } /* Examine each edge to see if we were able to prove any were not executable. If an edge is not executable, then we can remove its alternative in PHI nodes as the destination of the edge, we can simplify the conditional branch at the source of the edge, and we can remove the edge from the CFG. Note we do not delete unreachable blocks yet as the DF analyzer can not deal with that yet. */ static void optimize_unexecutable_edges (edges, executable_edges) struct edge_list *edges; sbitmap executable_edges; { int i; for (i = 0; i < NUM_EDGES (edges); i++) { if (!TEST_BIT (executable_edges, i)) { edge edge = INDEX_EDGE (edges, i); if (edge->flags & EDGE_ABNORMAL) continue; /* We found an edge that is not executable. First simplify the PHI nodes in the target block. */ if (edge->dest != EXIT_BLOCK_PTR) { rtx insn = first_insn_after_basic_block_note (edge->dest); while (PHI_NODE_P (insn)) { remove_phi_alternative (PATTERN (insn), edge->src); if (rtl_dump_file) fprintf (rtl_dump_file, "Removing alternative for bb %d of phi %d\n", edge->src->index, SSA_NAME (PATTERN (insn))); insn = NEXT_INSN (insn); } } if (rtl_dump_file) fprintf (rtl_dump_file, "Removing unexecutable edge from %d to %d\n", edge->src->index, edge->dest->index); /* Since the edge was not executable, remove it from the CFG. */ remove_edge (edge); } } /* We have removed all the unexecutable edges from the CFG. Fix up the conditional jumps at the end of any affected block. We have three cases to deal with: a. Both outgoing edges are not executable. This happens if the source block is not reachable. We will deal with this by deleting all the insns in the block later. b. The fall-thru edge is not executable. In this case we change the conditional jump into an unconditional jump and add a BARRIER after the unconditional jump. Note that since we are working on generic RTL we can change the jump in-place instead of dealing with the headache of reemitting the jump. c. The branch taken edge is not executable. In this case we turn the jump into (set (pc) (pc)) which is a nop-jump and we will remove the unrecognizable insn later. In cases B & C we are removing uses of registers, so make sure to note those changes for the DF analyzer. */ for (i = 0; i < n_basic_blocks; i++) { basic_block bb = BASIC_BLOCK (i); rtx insn = bb->end; edge edge = bb->succ; /* If we have no predecessors, then this block is unreachable and will be cleaned up when we remove unreachable blocks. */ if (bb->pred == NULL || GET_CODE (insn) != JUMP_INSN) continue; /* If this block ends in a conditional jump, but only has one successor, then the jump needs adjustment. */ if (condjump_p (insn) && ! simplejump_p (insn) && bb->succ && bb->succ->succ_next == NULL) { /* If the fallthru edge is the executable edge, then turn this jump into a nop jump, otherwise make it an unconditinoal jump to its target. */ if (edge->flags & EDGE_FALLTHRU) { PUT_CODE (insn, NOTE); NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; } else { SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (Pmode, JUMP_LABEL (insn)); emit_barrier_after (insn); INSN_CODE (insn) = -1; } /* Inform the DF analyzer that this insn changed. */ df_insn_modify (df_analyzer, BLOCK_FOR_INSN (insn), insn); } } } /* Perform substitution of known values for pseudo registers. ??? Note we do not do simplifications or constant folding here, it is unlikely that any significant simplifications can be done here anyway. Consider that if the simplification would result in an expression that produces a constant value that the value would have been discovered and recorded already. We perform two transformations. First, we initialize pseudos to their known constant values at their definition point. Second, we try to replace uses with the known constant value. */ static void ssa_ccp_substitute_constants () { unsigned int i; for (i = FIRST_PSEUDO_REGISTER; i < VARRAY_SIZE (ssa_definition); i++) { if (values[i].lattice_val == CONSTANT) { rtx def = VARRAY_RTX (ssa_definition, i); rtx set = single_set (def); struct df_link *curruse; if (! set) continue; /* Do not try to simplify PHI nodes down to a constant load. That will be done later as we translate out of SSA. Also, doing that here could violate the rule that all PHI nodes are consecutive at the start of the basic block. */ if (! PHI_NODE_P (def)) { if (rtl_dump_file) fprintf (rtl_dump_file, "Register %d is now set to a constant\n", SSA_NAME (PATTERN (def))); SET_SRC (set) = values[i].const_value; INSN_CODE (def) = -1; df_insn_modify (df_analyzer, BLOCK_FOR_INSN (def), def); } /* Iterate through all the uses of this entry and try replacements there too. Note it is not particularly profitable to try and fold/simplify expressions here as most of the common cases were handled above. */ for (curruse = df_analyzer->regs[i].uses; curruse; curruse = curruse->next) { rtx useinsn; useinsn = DF_REF_INSN (curruse->ref); if (!INSN_DELETED_P (useinsn) && ! (GET_CODE (useinsn) == NOTE && NOTE_LINE_NUMBER (useinsn) == NOTE_INSN_DELETED) && (GET_CODE (useinsn) == INSN || GET_CODE (useinsn) == JUMP_INSN)) { if (validate_replace_src (regno_reg_rtx [i], values[i].const_value, useinsn)) { if (rtl_dump_file) fprintf (rtl_dump_file, "Register %d in insn %d replaced with constant\n", i, INSN_UID (useinsn)); INSN_CODE (useinsn) = -1; df_insn_modify (df_analyzer, BLOCK_FOR_INSN (useinsn), useinsn); } } } } } } /* Now find all unreachable basic blocks. All the insns in those blocks are unreachable, so delete them and mark any necessary updates for the DF analyzer. */ static void ssa_ccp_df_delete_unreachable_insns () { int i; /* Use the CFG to find all the reachable blocks. */ find_unreachable_blocks (); /* Now we know what blocks are not reachable. Mark all the insns in those blocks as deleted for the DF analyzer. We'll let the normal flow code actually remove the unreachable blocks. */ for (i = n_basic_blocks - 1; i >= 0; --i) { basic_block b = BASIC_BLOCK (i); if (b->aux != NULL) /* This block was found. Tidy up the mark. */ b->aux = NULL; else { rtx start = b->head; rtx end = b->end; rtx tmp; /* Include any jump table following the basic block. */ end = b->end; if (GET_CODE (end) == JUMP_INSN && (tmp = JUMP_LABEL (end)) != NULL_RTX && (tmp = NEXT_INSN (tmp)) != NULL_RTX && GET_CODE (tmp) == JUMP_INSN && (GET_CODE (PATTERN (tmp)) == ADDR_VEC || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC)) end = tmp; while (1) { rtx next = NEXT_INSN (start); if (GET_CODE (start) == INSN || GET_CODE (start) == CALL_INSN || GET_CODE (start) == JUMP_INSN) df_insn_delete (df_analyzer, BLOCK_FOR_INSN (start), start); if (start == end) break; start = next; } } } } /* Main entry point for SSA Conditional Constant Propagation. Long term it should accept as input the specific flow graph to operate on so that it can be called for sub-graphs. */ void ssa_const_prop (void) { unsigned int i; edge curredge; /* We need alias analysis (for what?) */ init_alias_analysis (); df_analyzer = df_init (); df_analyse (df_analyzer, 0, DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS); /* We need mappings from insn to its containing block. */ compute_bb_for_insn (get_max_uid ()); /* Perform a quick and dirty dead code elimination pass. This is not as aggressive as it could be, but it's good enough to clean up a lot of unwanted junk and it is fast. */ ssa_fast_dce (df_analyzer); /* Build an edge list from the CFG. */ edges = create_edge_list (); /* Initialize the values array with everything as undefined. */ values = (value *) xmalloc (VARRAY_SIZE (ssa_definition) * sizeof (value)); for (i = 0; i < VARRAY_SIZE (ssa_definition); i++) { if (i < FIRST_PSEUDO_REGISTER) values[i].lattice_val = VARYING; else values[i].lattice_val = UNDEFINED; values[i].const_value = NULL; } ssa_edges = sbitmap_alloc (VARRAY_SIZE (ssa_definition)); sbitmap_zero (ssa_edges); executable_blocks = sbitmap_alloc (n_basic_blocks); sbitmap_zero (executable_blocks); executable_edges = sbitmap_alloc (NUM_EDGES (edges)); sbitmap_zero (executable_edges); edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge)); flow_edges = ENTRY_BLOCK_PTR->succ; /* Add the successors of the entry block to the edge worklist. That is enough of a seed to get SSA-CCP started. */ for (curredge = ENTRY_BLOCK_PTR->succ; curredge; curredge = curredge->succ_next) { int index = EIE (curredge->src, curredge->dest); SET_BIT (executable_edges, index); edge_info[index] = curredge->succ_next; } /* Iterate until until the worklists are empty. */ do { examine_flow_edges (); follow_def_use_chains (); } while (flow_edges != NULL); /* Now perform substitutions based on the known constant values. */ ssa_ccp_substitute_constants (); /* Remove unexecutable edges from the CFG and make appropriate adjustments to PHI nodes. */ optimize_unexecutable_edges (edges, executable_edges); /* Now remove all unreachable insns and update the DF information. as appropriate. */ ssa_ccp_df_delete_unreachable_insns (); #if 0 /* The DF analyzer expects the number of blocks to remain constant, so we can't remove unreachable blocks. Code the DF analyzer calls expects there to be no unreachable blocks in the CFG. So we can't leave unreachable blocks in the CFG. So, there is no way to do an incremental update of the DF data at this point. */ df_analyse (df_analyzer, 0, DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS); #endif /* Clean up any dead code exposed by SSA-CCP, do this after updating the dataflow information! */ ssa_fast_dce (df_analyzer); free (values); values = NULL; free (edge_info); edge_info = NULL; sbitmap_free (executable_blocks); executable_blocks = NULL; free_edge_list (edges); edges = NULL; sbitmap_free (executable_edges); executable_edges = NULL; df_finish (df_analyzer); end_alias_analysis (); } static int mark_references (current_rtx, data) rtx *current_rtx; void *data; { rtx x = *current_rtx; sbitmap worklist = (sbitmap)data; if (x == NULL_RTX) return 0; if (GET_CODE (x) == SET) { rtx dest = SET_DEST (x); if (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG || GET_CODE (dest) == SIGN_EXTRACT || GET_CODE (dest) == ZERO_EXTRACT) { rtx reg; reg = dest; while (GET_CODE (reg) == STRICT_LOW_PART || GET_CODE (reg) == SUBREG || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT) reg = XEXP (reg, 0); if (GET_CODE (reg) == REG) SET_BIT (worklist, REGNO (reg)); } if (GET_CODE (dest) == REG) { for_each_rtx (&SET_SRC (x), mark_references, data); return -1; } return 0; } else if (GET_CODE (x) == REG) { SET_BIT (worklist, REGNO (x)); return -1; } else if (GET_CODE (x) == CLOBBER) return -1; else return 0; } static void ssa_fast_dce (df) struct df *df; { sbitmap worklist = sbitmap_alloc (VARRAY_SIZE (ssa_definition)); sbitmap_ones (worklist); /* Iterate on the worklist until there's no definitions left to examine. */ while (sbitmap_first_set_bit (worklist) >= 0) { struct df_link *curruse; int reg, found_use; /* Remove an item from the worklist. */ reg = sbitmap_first_set_bit (worklist); RESET_BIT (worklist, reg); /* We never consider deleting assignments to hard regs or things which do not have SSA definitions, or things we have already deleted, or things with unusual side effects. */ if (reg < FIRST_PSEUDO_REGISTER || ! VARRAY_RTX (ssa_definition, reg) || INSN_DELETED_P (VARRAY_RTX (ssa_definition, reg)) || (GET_CODE (VARRAY_RTX (ssa_definition, reg)) == NOTE && (NOTE_LINE_NUMBER (VARRAY_RTX (ssa_definition, reg)) == NOTE_INSN_DELETED)) || side_effects_p (PATTERN (VARRAY_RTX (ssa_definition, reg)))) continue; /* Iterate over the uses of this register. If we can not find any uses that have not been deleted, then the definition of this register is dead. */ found_use = 0; for (curruse = df->regs[reg].uses; curruse; curruse = curruse->next) { if (curruse->ref && DF_REF_INSN (curruse->ref) && ! INSN_DELETED_P (DF_REF_INSN (curruse->ref)) && ! (GET_CODE (DF_REF_INSN (curruse->ref)) == NOTE && (NOTE_LINE_NUMBER (DF_REF_INSN (curruse->ref)) == NOTE_INSN_DELETED)) && DF_REF_INSN (curruse->ref) != VARRAY_RTX (ssa_definition, reg)) { found_use = 1; break; } } /* If we did not find a use of this register, then the definition of this register is dead. */ if (! found_use) { rtx def = VARRAY_RTX (ssa_definition, reg); /* Add all registers referenced by INSN to the work list. */ for_each_rtx (&PATTERN (def), mark_references, worklist); /* Inform the analyzer that this insn is going to be deleted. */ df_insn_delete (df, BLOCK_FOR_INSN (def), def); if (PHI_NODE_P (def)) { if (def == BLOCK_FOR_INSN (def)->head && def == BLOCK_FOR_INSN (def)->end) { /* Delete it. */ PUT_CODE (def, NOTE); NOTE_LINE_NUMBER (def) = NOTE_INSN_DELETED; } else if (def == BLOCK_FOR_INSN (def)->head) { BLOCK_FOR_INSN (def)->head = NEXT_INSN (def); flow_delete_insn (def); } else if (def == BLOCK_FOR_INSN (def)->end) { BLOCK_FOR_INSN (def)->end = PREV_INSN (def); flow_delete_insn (def); } else flow_delete_insn (def); } else { flow_delete_insn (def); } VARRAY_RTX (ssa_definition, reg) = NULL; } } sbitmap_free (worklist); }