=================================================================== RCS file: /cvsroot/gcc/gcc/gcc/Makefile.in,v retrieving revision 1.1402 diff -c -3 -p -r1.1402 Makefile.in *** Makefile.in 27 Sep 2004 23:16:29 -0000 1.1402 --- Makefile.in 28 Sep 2004 11:31:41 -0000 *************** loop-unswitch.o : loop-unswitch.c $(CONF *** 2037,2043 **** output.h $(EXPR_H) coretypes.h $(TM_H) loop-unroll.o: loop-unroll.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TM_H) \ $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) $(PARAMS_H) \ ! output.h $(EXPR_H) coretypes.h $(TM_H) $(HASHTAB_H) $(RECOG_H) dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ hard-reg-set.h $(BASIC_BLOCK_H) et-forest.h et-forest.o : et-forest.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) et-forest.h alloc-pool.h --- 2037,2043 ---- output.h $(EXPR_H) coretypes.h $(TM_H) loop-unroll.o: loop-unroll.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TM_H) \ $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) $(PARAMS_H) \ ! output.h $(EXPR_H) coretypes.h $(TM_H) $(HASHTAB_H) $(RECOG_H) $(VARRAY_H) dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ hard-reg-set.h $(BASIC_BLOCK_H) et-forest.h et-forest.o : et-forest.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) et-forest.h alloc-pool.h Index: common.opt =================================================================== RCS file: /cvsroot/gcc/gcc/gcc/common.opt,v retrieving revision 1.55 diff -c -3 -p -r1.55 common.opt *** common.opt 14 Sep 2004 08:05:45 -0000 1.55 --- common.opt 28 Sep 2004 11:31:41 -0000 *************** fsplit-ivs-in-unroller *** 748,753 **** --- 748,757 ---- Common Report Var(flag_split_ivs_in_unroller) Init(1) Split lifetimes of induction variables when loops are unrolled. + fvariable-expansion-in-unroller + Common Report Var(flag_variable_expansion_in_unroller) + Apply variable expansion when loops are unrolled. + ; Emit code to probe the stack, to help detect stack overflow; also ; may cause large objects to be allocated dynamically. fstack-check Index: loop-unroll.c =================================================================== RCS file: /cvsroot/gcc/gcc/gcc/loop-unroll.c,v retrieving revision 1.20 diff -c -3 -p -r1.20 loop-unroll.c *** loop-unroll.c 28 Sep 2004 07:59:48 -0000 1.20 --- loop-unroll.c 28 Sep 2004 11:31:42 -0000 *************** Software Foundation, 59 Temple Place - S *** 31,37 **** #include "output.h" #include "expr.h" #include "hashtab.h" ! #include "recog.h" /* This pass performs loop unrolling and peeling. We only perform these optimizations on innermost loops (with single exception) because --- 31,38 ---- #include "output.h" #include "expr.h" #include "hashtab.h" ! #include "recog.h" ! #include "varray.h" /* This pass performs loop unrolling and peeling. We only perform these optimizations on innermost loops (with single exception) because *************** struct iv_to_split *** 83,93 **** XEXP (XEXP (single_set, loc[0]), loc[1]). */ }; ! struct split_ivs_info { ! htab_t insns_to_split; /* A hashtable of insns to split. */ ! unsigned first_new_block; /* The first basic block that was ! duplicated. */ }; static void decide_unrolling_and_peeling (struct loops *, int); --- 84,115 ---- XEXP (XEXP (single_set, loc[0]), loc[1]). */ }; ! /* Information about accumulators to expand. */ ! ! struct var_to_expand ! { ! rtx insn; /* The insn in that the variable expansion occurs. */ ! rtx reg; /* The accumulator which is expanded. */ ! varray_type var_expansions; /* The copies of the accumulator which is expanded. */ ! enum rtx_code op; /* The type of the accumulation - addition, subtraction ! or multiplication. */ ! int expansion_count; /* Count the number of expansions generated so far. */ ! int last_used_expansion; /* Record the last variable which used to expand ! the accumulator. */ ! }; ! ! /* Information about optimization applied in ! the unrolled loop. */ ! ! struct opt_info { ! htab_t insns_to_split; /* A hashtable of insns to split. */ ! htab_t insns_with_var_to_expand; /* A hashtable of insns with accumulators ! to expand. */ ! unsigned first_new_block; /* The first basic block that was ! duplicated. */ ! basic_block loop_exit; /* The loop exit basic block. */ ! basic_block loop_preheader; /* The loop preheader basic block. */ }; static void decide_unrolling_and_peeling (struct loops *, int); *************** static void peel_loop_completely (struct *** 103,112 **** static void unroll_loop_stupid (struct loops *, struct loop *); static void unroll_loop_constant_iterations (struct loops *, struct loop *); static void unroll_loop_runtime_iterations (struct loops *, struct loop *); ! static struct split_ivs_info *analyze_ivs_to_split (struct loop *); ! static void si_info_start_duplication (struct split_ivs_info *); ! static void split_ivs_in_copies (struct split_ivs_info *, unsigned, bool, bool); ! static void free_si_info (struct split_ivs_info *); /* Unroll and/or peel (depending on FLAGS) LOOPS. */ void --- 125,142 ---- static void unroll_loop_stupid (struct loops *, struct loop *); static void unroll_loop_constant_iterations (struct loops *, struct loop *); static void unroll_loop_runtime_iterations (struct loops *, struct loop *); ! static struct opt_info *analyze_insns_in_loop (struct loop *); ! static void opt_info_start_duplication (struct opt_info *); ! static void apply_opt_in_copies (struct opt_info *, unsigned, bool, bool); ! static void free_opt_info (struct opt_info *); ! static struct var_to_expand *analyze_insn_to_expand_var (struct loop*, rtx); ! static bool referenced_in_one_insn_in_loop_p (struct loop *, rtx); ! static struct iv_to_split *analyze_iv_to_split_insn (rtx); ! static void expand_var_during_unrolling (struct var_to_expand *, rtx); ! static int insert_var_expansion_initialization (void **, void *); ! static int combine_var_copies_in_loop_exit (void **, void *); ! static int release_var_copies (void **, void *); ! static rtx get_expansion (struct var_to_expand *); /* Unroll and/or peel (depending on FLAGS) LOOPS. */ void *************** peel_loop_completely (struct loops *loop *** 456,463 **** unsigned n_remove_edges, i; edge *remove_edges, ein; struct niter_desc *desc = get_simple_loop_desc (loop); ! struct split_ivs_info *si_info = NULL; ! npeel = desc->niter; if (npeel) --- 486,493 ---- unsigned n_remove_edges, i; edge *remove_edges, ein; struct niter_desc *desc = get_simple_loop_desc (loop); ! struct opt_info *opt_info = NULL; ! npeel = desc->niter; if (npeel) *************** peel_loop_completely (struct loops *loop *** 472,480 **** n_remove_edges = 0; if (flag_split_ivs_in_unroller) ! si_info = analyze_ivs_to_split (loop); ! ! si_info_start_duplication (si_info); if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), loops, npeel, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, --- 502,510 ---- n_remove_edges = 0; if (flag_split_ivs_in_unroller) ! opt_info = analyze_insns_in_loop (loop); ! ! opt_info_start_duplication (opt_info); if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), loops, npeel, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, *************** peel_loop_completely (struct loops *loop *** 482,493 **** abort (); free (wont_exit); ! ! if (si_info) ! { ! split_ivs_in_copies (si_info, npeel, false, true); ! free_si_info (si_info); ! } /* Remove the exit edges. */ for (i = 0; i < n_remove_edges; i++) --- 512,523 ---- abort (); free (wont_exit); ! ! if (opt_info) ! { ! apply_opt_in_copies (opt_info, npeel, false, true); ! free_opt_info (opt_info); ! } /* Remove the exit edges. */ for (i = 0; i < n_remove_edges; i++) *************** unroll_loop_constant_iterations (struct *** 636,643 **** unsigned max_unroll = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); bool exit_at_end = loop_exit_at_end_p (loop); ! struct split_ivs_info *si_info = NULL; ! niter = desc->niter; /* Should not get here (such loop should be peeled instead). */ --- 666,673 ---- unsigned max_unroll = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); bool exit_at_end = loop_exit_at_end_p (loop); ! struct opt_info *opt_info = NULL; ! niter = desc->niter; /* Should not get here (such loop should be peeled instead). */ *************** unroll_loop_constant_iterations (struct *** 650,659 **** remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge)); n_remove_edges = 0; ! ! if (flag_split_ivs_in_unroller) ! si_info = analyze_ivs_to_split (loop); ! if (!exit_at_end) { /* The exit is not at the end of the loop; leave exit test --- 680,689 ---- remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge)); n_remove_edges = 0; ! if (flag_split_ivs_in_unroller ! || flag_variable_expansion_in_unroller) ! opt_info = analyze_insns_in_loop (loop); ! if (!exit_at_end) { /* The exit is not at the end of the loop; leave exit test *************** unroll_loop_constant_iterations (struct *** 670,686 **** if (exit_mod) { ! si_info_start_duplication (si_info); ! if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), loops, exit_mod, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! if (si_info && exit_mod > 1) ! split_ivs_in_copies (si_info, exit_mod, false, false); ! desc->noloop_assumptions = NULL_RTX; desc->niter -= exit_mod; desc->niter_max -= exit_mod; --- 700,716 ---- if (exit_mod) { ! opt_info_start_duplication (opt_info); ! if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), loops, exit_mod, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! if (opt_info && exit_mod > 1) ! apply_opt_in_copies (opt_info, exit_mod, false, false); ! desc->noloop_assumptions = NULL_RTX; desc->niter -= exit_mod; desc->niter_max -= exit_mod; *************** unroll_loop_constant_iterations (struct *** 705,720 **** RESET_BIT (wont_exit, 0); if (desc->noloop_assumptions) RESET_BIT (wont_exit, 1); ! ! si_info_start_duplication (si_info); if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), loops, exit_mod + 1, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! ! if (si_info && exit_mod > 0) ! split_ivs_in_copies (si_info, exit_mod + 1, false, false); desc->niter -= exit_mod + 1; desc->niter_max -= exit_mod + 1; --- 735,750 ---- RESET_BIT (wont_exit, 0); if (desc->noloop_assumptions) RESET_BIT (wont_exit, 1); ! ! opt_info_start_duplication (opt_info); if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), loops, exit_mod + 1, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! ! if (opt_info && exit_mod > 0) ! apply_opt_in_copies (opt_info, exit_mod + 1, false, false); desc->niter -= exit_mod + 1; desc->niter_max -= exit_mod + 1; *************** unroll_loop_constant_iterations (struct *** 728,744 **** } /* Now unroll the loop. */ ! si_info_start_duplication (si_info); if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), loops, max_unroll, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! if (si_info) { ! split_ivs_in_copies (si_info, max_unroll, true, true); ! free_si_info (si_info); } free (wont_exit); --- 758,775 ---- } /* Now unroll the loop. */ ! ! opt_info_start_duplication (opt_info); if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), loops, max_unroll, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! if (opt_info) { ! apply_opt_in_copies (opt_info, max_unroll, true, true); ! free_opt_info (opt_info); } free (wont_exit); *************** unroll_loop_runtime_iterations (struct l *** 900,910 **** unsigned max_unroll = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); bool exit_at_end = loop_exit_at_end_p (loop); ! struct split_ivs_info *si_info = NULL; ! ! if (flag_split_ivs_in_unroller) ! si_info = analyze_ivs_to_split (loop); ! /* Remember blocks whose dominators will have to be updated. */ dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); n_dom_bbs = 0; --- 931,942 ---- unsigned max_unroll = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); bool exit_at_end = loop_exit_at_end_p (loop); ! struct opt_info *opt_info = NULL; ! ! if (flag_split_ivs_in_unroller ! || flag_variable_expansion_in_unroller) ! opt_info = analyze_insns_in_loop (loop); ! /* Remember blocks whose dominators will have to be updated. */ dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); n_dom_bbs = 0; *************** unroll_loop_runtime_iterations (struct l *** 1040,1057 **** sbitmap_ones (wont_exit); RESET_BIT (wont_exit, may_exit_copy); ! ! si_info_start_duplication (si_info); if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), loops, max_unroll, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! ! if (si_info) { ! split_ivs_in_copies (si_info, max_unroll, true, true); ! free_si_info (si_info); } free (wont_exit); --- 1072,1089 ---- sbitmap_ones (wont_exit); RESET_BIT (wont_exit, may_exit_copy); ! opt_info_start_duplication (opt_info); ! if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), loops, max_unroll, wont_exit, desc->out_edge, remove_edges, &n_remove_edges, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! ! if (opt_info) { ! apply_opt_in_copies (opt_info, max_unroll, true, true); ! free_opt_info (opt_info); } free (wont_exit); *************** peel_loop_simple (struct loops *loops, s *** 1206,1231 **** sbitmap wont_exit; unsigned npeel = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); ! struct split_ivs_info *si_info = NULL; ! if (flag_split_ivs_in_unroller && npeel > 1) ! si_info = analyze_ivs_to_split (loop); ! wont_exit = sbitmap_alloc (npeel + 1); sbitmap_zero (wont_exit); ! ! si_info_start_duplication (si_info); if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), loops, npeel, wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ)) abort (); free (wont_exit); ! ! if (si_info) { ! split_ivs_in_copies (si_info, npeel, false, false); ! free_si_info (si_info); } if (desc->simple_p) --- 1238,1264 ---- sbitmap wont_exit; unsigned npeel = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); ! struct opt_info *opt_info = NULL; ! if (flag_split_ivs_in_unroller && npeel > 1) ! opt_info = analyze_insns_in_loop (loop); ! wont_exit = sbitmap_alloc (npeel + 1); sbitmap_zero (wont_exit); ! ! opt_info_start_duplication (opt_info); ! if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), loops, npeel, wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ)) abort (); free (wont_exit); ! ! if (opt_info) { ! apply_opt_in_copies (opt_info, npeel, false, false); ! free_opt_info (opt_info); } if (desc->simple_p) *************** unroll_loop_stupid (struct loops *loops, *** 1350,1373 **** sbitmap wont_exit; unsigned nunroll = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); ! struct split_ivs_info *si_info = NULL; ! ! if (flag_split_ivs_in_unroller) ! si_info = analyze_ivs_to_split (loop); ! wont_exit = sbitmap_alloc (nunroll + 1); sbitmap_zero (wont_exit); ! ! si_info_start_duplication (si_info); if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), loops, nunroll, wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! ! if (si_info) { ! split_ivs_in_copies (si_info, nunroll, true, true); ! free_si_info (si_info); } free (wont_exit); --- 1383,1408 ---- sbitmap wont_exit; unsigned nunroll = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); ! struct opt_info *opt_info = NULL; ! ! if (flag_split_ivs_in_unroller ! || flag_variable_expansion_in_unroller) ! opt_info = analyze_insns_in_loop (loop); ! ! wont_exit = sbitmap_alloc (nunroll + 1); sbitmap_zero (wont_exit); ! opt_info_start_duplication (opt_info); ! if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), loops, nunroll, wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ)) abort (); ! ! if (opt_info) { ! apply_opt_in_copies (opt_info, nunroll, true, true); ! free_opt_info (opt_info); } free (wont_exit); *************** si_info_eq (const void *ivts1, const voi *** 1407,1416 **** return i1->insn == i2->insn; } /* Determine whether there is an induction variable in INSN that ! we would like to split during unrolling. Return NULL if INSN ! contains no interesting IVs. Otherwise, allocate an IV_TO_SPLIT ! structure, fill it with the relevant information and return a pointer to it. */ static struct iv_to_split * --- 1442,1594 ---- return i1->insn == i2->insn; } + /* An hash function for information about insns which contains + accumulators to expand. */ + + static hashval_t + ve_info_hash (const void *ves) + { + return htab_hash_pointer (((struct var_to_expand *) ves)->insn); + } + + /* An equality functions for information about insns which contains + accumulators to expand. */ + + static int + ve_info_eq (const void *ivts1, const void *ivts2) + { + const struct var_to_expand *i1 = ivts1; + const struct var_to_expand *i2 = ivts2; + + return i1->insn == i2->insn; + } + + /* Returns true if REG is referenced in one insn in LOOP. */ + + bool + referenced_in_one_insn_in_loop_p (struct loop *loop, rtx reg) + { + basic_block *body, bb; + unsigned i; + int count_ref = 0; + rtx insn; + + body = get_loop_body (loop); + for (i = 0; i < loop->num_nodes; i++) + { + bb = body[i]; + + FOR_BB_INSNS (bb, insn) + { + if (rtx_referenced_p (reg, insn)) + count_ref++; + } + } + return (count_ref == 1); + } + + /* Determine whether INSN contains an accumulator + which can be expanded into separate copies, + one for each copy of the LOOP body. + + for (i = 0 ; i < n; i++) + sum += a[i]; + + ==> + + sum += a[i] + .... + i = i+1; + sum1 += a[i] + .... + i = i+1 + sum2 += a[i]; + .... + + Return NULL if INSN contains no opportunity for expansion of accumulator. + Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant + information and return a pointer to it. + */ + + static struct var_to_expand * + analyze_insn_to_expand_var (struct loop *loop, rtx insn) + { + rtx set, dest, src, op1; + struct var_to_expand *ves; + enum machine_mode mode1, mode2; + + set = single_set (insn); + if (!set) + return NULL; + + dest = SET_DEST (set); + src = SET_SRC (set); + + if (GET_CODE (src) != PLUS + && GET_CODE (src) != MINUS + && GET_CODE (src) != MULT) + return NULL; + + if (!XEXP (src, 0)) + return NULL; + + op1 = XEXP (src, 0); + + if (!REG_P (dest) + && !(GET_CODE (dest) == SUBREG + && REG_P (SUBREG_REG (dest)))) + return NULL; + + if (!rtx_equal_p (dest, op1)) + return NULL; + + if (!referenced_in_one_insn_in_loop_p (loop, dest)) + return NULL; + + if (rtx_referenced_p (dest, XEXP (src, 1))) + return NULL; + + mode1 = GET_MODE (dest); + mode2 = GET_MODE (XEXP (src, 1)); + if ((FLOAT_MODE_P (mode1) + || FLOAT_MODE_P (mode2)) + && !flag_unsafe_math_optimizations) + return NULL; + + /* Record the accumulator to expand. */ + ves = xmalloc (sizeof (struct var_to_expand)); + ves->insn = insn; + VARRAY_RTX_INIT (ves->var_expansions, 1, "var_expansions"); + ves->reg = copy_rtx (dest); + ves->op = GET_CODE (src); + ves->expansion_count = 0; + ves->last_used_expansion = 0; + return ves; + } + /* Determine whether there is an induction variable in INSN that ! we would like to split during unrolling. ! ! I.e. replace ! ! i = i + 1; ! ... ! i = i + 1; ! ... ! i = i + 1; ! ... ! ! type chains by ! ! i0 = i + 1 ! ... ! i = i0 + 1 ! ... ! i = i0 + 2 ! ... ! ! Return NULL if INSN contains no interesting IVs. Otherwise, allocate ! an IV_TO_SPLIT structure, fill it with the relevant information and return a pointer to it. */ static struct iv_to_split * *************** analyze_iv_to_split_insn (rtx insn) *** 1451,1477 **** return ivts; } ! /* Determines which of induction variables in LOOP to split. ! Return a SPLIT_IVS_INFO struct with the hash table filled ! with all insns to split IVs in. The FIRST_NEW_BLOCK field is undefined for the return value. */ ! static struct split_ivs_info * ! analyze_ivs_to_split (struct loop *loop) { basic_block *body, bb; ! unsigned i; ! struct split_ivs_info *si_info = xcalloc (1, sizeof (struct split_ivs_info)); rtx insn; ! struct iv_to_split *ivts; ! PTR *slot; ! ! si_info->insns_to_split = htab_create (5 * loop->num_nodes, ! si_info_hash, si_info_eq, free); ! iv_analysis_loop_init (loop); body = get_loop_body (loop); for (i = 0; i < loop->num_nodes; i++) { bb = body[i]; --- 1629,1686 ---- return ivts; } ! /* Determines which of insns in LOOP can be optimized. ! Return a OPT_INFO struct with the relevant hash tables filled ! with all insns to be optimized. The FIRST_NEW_BLOCK field is undefined for the return value. */ ! static struct opt_info * ! analyze_insns_in_loop (struct loop *loop) { basic_block *body, bb; ! unsigned i, n_edges = 0; ! struct opt_info *opt_info = xcalloc (1, sizeof (struct opt_info)); rtx insn; ! struct iv_to_split *ivts = NULL; ! struct var_to_expand *ves = NULL; ! PTR *slot1; ! PTR *slot2; ! edge *edges = get_loop_exit_edges (loop, &n_edges); ! basic_block preheader; ! bool can_apply = false; ! iv_analysis_loop_init (loop); body = get_loop_body (loop); + + if (flag_split_ivs_in_unroller) + opt_info->insns_to_split = htab_create (5 * loop->num_nodes, + si_info_hash, si_info_eq, free); + + /* Record the loop exit bb and loop preheader before the unrolling. */ + if (!loop_preheader_edge (loop)->src) + { + preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX); + opt_info->loop_preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX); + } + else + opt_info->loop_preheader = loop_preheader_edge (loop)->src; + + if (n_edges == 1 + && !(edges[0]->flags & EDGE_COMPLEX) + && (edges[0]->flags & EDGE_LOOP_EXIT)) + { + opt_info->loop_exit = loop_split_edge_with (edges[0], NULL_RTX); + can_apply = true; + } + + if (flag_variable_expansion_in_unroller + && can_apply) + { + opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes, + ve_info_hash, ve_info_eq, free); + } + for (i = 0; i < loop->num_nodes; i++) { bb = body[i]; *************** analyze_ivs_to_split (struct loop *loop) *** 1479,1511 **** continue; FOR_BB_INSNS (bb, insn) ! { ! if (!INSN_P (insn)) ! continue; ! ! ivts = analyze_iv_to_split_insn (insn); ! ! if (!ivts) ! continue; ! ! slot = htab_find_slot (si_info->insns_to_split, ivts, INSERT); ! *slot = ivts; ! } } ! free (body); ! ! return si_info; } /* Called just before loop duplication. Records start of duplicated area ! to SI_INFO. */ static void ! si_info_start_duplication (struct split_ivs_info *si_info) { ! if (si_info) ! si_info->first_new_block = last_basic_block; } /* Determine the number of iterations between initialization of the base --- 1688,1731 ---- continue; FOR_BB_INSNS (bb, insn) ! { ! if (!INSN_P (insn)) ! continue; ! ! if (opt_info->insns_to_split) ! ivts = analyze_iv_to_split_insn (insn); ! ! if (ivts) ! { ! slot1 = htab_find_slot (opt_info->insns_to_split, ivts, INSERT); ! *slot1 = ivts; ! continue; ! } ! ! if (opt_info->insns_with_var_to_expand) ! ves = analyze_insn_to_expand_var (loop, insn); ! ! if (ves) ! { ! slot2 = htab_find_slot (opt_info->insns_with_var_to_expand, ves, INSERT); ! *slot2 = ves; ! } ! } } ! ! free (edges); free (body); ! return opt_info; } /* Called just before loop duplication. Records start of duplicated area ! to OPT_INFO. */ static void ! opt_info_start_duplication (struct opt_info *opt_info) { ! if (opt_info) ! opt_info->first_new_block = last_basic_block; } /* Determine the number of iterations between initialization of the base *************** split_iv (struct iv_to_split *ivts, rtx *** 1641,1761 **** delete_insn (insn); } - /* Splits induction variables (that are marked in SI_INFO) in copies of loop. - I.e. replace ! i = i + 1; ! ... ! i = i + 1; ! ... ! i = i + 1; ! ... ! type chains by - i0 = i + 1 - ... - i = i0 + 1 - ... - i = i0 + 2 - ... UNROLLING is true if we unrolled (not peeled) the loop. REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of the loop (as it should happen in complete unrolling, but not in ordinary peeling of the loop). */ static void ! split_ivs_in_copies (struct split_ivs_info *si_info, unsigned n_copies, ! bool unrolling, bool rewrite_original_loop) { unsigned i, delta; basic_block bb, orig_bb; rtx insn, orig_insn, next; struct iv_to_split ivts_templ, *ivts; ! /* Sanity check -- we need to put initialization in the original loop body. */ gcc_assert (!unrolling || rewrite_original_loop); ! /* Allocate the basic variables (i0). */ ! htab_traverse (si_info->insns_to_split, allocate_basic_variable, NULL); ! ! for (i = si_info->first_new_block; i < (unsigned) last_basic_block; i++) { bb = BASIC_BLOCK (i); orig_bb = bb->rbi->original; ! delta = determine_split_iv_delta (bb->rbi->copy_number, n_copies, unrolling); orig_insn = BB_HEAD (orig_bb); for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next) ! { ! next = NEXT_INSN (insn); ! if (!INSN_P (insn)) ! continue; ! ! while (!INSN_P (orig_insn)) ! orig_insn = NEXT_INSN (orig_insn); ! ! ivts_templ.insn = orig_insn; ! ivts = htab_find (si_info->insns_to_split, &ivts_templ); ! if (ivts) ! { ! #ifdef ENABLE_CHECKING ! if (!rtx_equal_p (PATTERN (insn), PATTERN (orig_insn))) ! abort (); #endif ! ! if (!delta) ! insert_base_initialization (ivts, insn); ! split_iv (ivts, insn, delta); ! } ! orig_insn = NEXT_INSN (orig_insn); ! } } if (!rewrite_original_loop) return; ! /* Rewrite also the original loop body. Find them as originals of the blocks in the last copied iteration, i.e. those that have bb->rbi->original->copy == bb. */ ! for (i = si_info->first_new_block; i < (unsigned) last_basic_block; i++) { bb = BASIC_BLOCK (i); orig_bb = bb->rbi->original; if (orig_bb->rbi->copy != bb) continue; ! delta = determine_split_iv_delta (0, n_copies, unrolling); for (orig_insn = BB_HEAD (orig_bb); ! orig_insn != NEXT_INSN (BB_END (bb)); ! orig_insn = next) ! { ! next = NEXT_INSN (orig_insn); ! if (!INSN_P (orig_insn)) ! continue; ! ivts_templ.insn = orig_insn; ! ivts = htab_find (si_info->insns_to_split, &ivts_templ); ! if (!ivts) ! continue; ! ! if (!delta) ! insert_base_initialization (ivts, orig_insn); ! split_iv (ivts, orig_insn, delta); ! } ! } } ! /* Release SI_INFO. */ static void ! free_si_info (struct split_ivs_info *si_info) { ! htab_delete (si_info->insns_to_split); ! free (si_info); } --- 1861,2177 ---- delete_insn (insn); } ! /* Return one expansion of the accumulator recoreded ! in struct VE. */ ! static rtx ! get_expansion (struct var_to_expand *ve) ! { ! rtx reg; ! ! if (ve->last_used_expansion == 0) ! reg = ve->reg; ! else ! reg = VARRAY_RTX (ve->var_expansions, ve->last_used_expansion - 1); ! ! if (VARRAY_ACTIVE_SIZE (ve->var_expansions) == (unsigned) ve->last_used_expansion) ! ve->last_used_expansion = 0; ! else ! ve->last_used_expansion++; ! ! return reg; ! } + /* Given INSN replace the uses of the accumulator recorded in VE + with a new register. */ + + static void + expand_var_during_unrolling (struct var_to_expand *ve, rtx insn) + { + rtx new_reg, set; + bool really_new_expansion = false; + + set = single_set (insn); + if (!set) + abort (); + + /* Generate a new register only if the expansion limit has not been + reached. Else reuse an already existing expansion. */ + if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS) > ve->expansion_count) + { + really_new_expansion = true; + new_reg = gen_reg_rtx (GET_MODE (ve->reg)); + } + else + new_reg = get_expansion (ve); + + validate_change (insn, &SET_DEST (set), new_reg, 1); + validate_change (insn, &XEXP (SET_SRC (set), 0), new_reg, 1); + + if (apply_change_group ()) + if (really_new_expansion) + { + VARRAY_PUSH_RTX (ve->var_expansions, new_reg); + ve->expansion_count++; + } + } + + /* Initialize the variable expansions in loop preheader. + Callbacks for htab_traverse. PLACE_P is the loop-preheader + basic block where the initializtion of the expansions + should take place. */ + + static int + insert_var_expansion_initialization (void **slot, void *place_p) + { + struct var_to_expand *ve = *slot; + basic_block place = (basic_block)place_p; + rtx seq, var, zero_init, insn; + unsigned i; + + if (VARRAY_ACTIVE_SIZE (ve->var_expansions) == 0) + return 1; + + start_sequence (); + if (ve->op == PLUS || ve->op == MINUS) + for (i = 0; i < VARRAY_ACTIVE_SIZE (ve->var_expansions); i++) + { + var = VARRAY_RTX (ve->var_expansions, i); + zero_init = CONST0_RTX (GET_MODE (var)); + emit_move_insn (var, zero_init); + } + else if (ve->op == MULT) + for (i = 0; i < VARRAY_ACTIVE_SIZE (ve->var_expansions); i++) + { + var = VARRAY_RTX (ve->var_expansions, i); + zero_init = CONST1_RTX (GET_MODE (var)); + emit_move_insn (var, zero_init); + } + + seq = get_insns (); + end_sequence (); + + insn = BB_HEAD (place); + while (!NOTE_INSN_BASIC_BLOCK_P (insn)) + insn = NEXT_INSN (insn); + + emit_insn_after (seq, insn); + /* Continue traversing the hash table. */ + return 1; + } + + /* Combine the variable expansions at the loop exit. + Callbacks for htab_traverse. PLACE_P is the loop exit + basic block where the summation of the expansions should + take place. */ + + static int + combine_var_copies_in_loop_exit (void **slot, void *place_p) + { + struct var_to_expand *ve = *slot; + basic_block place = (basic_block)place_p; + rtx sum = ve->reg; + rtx expr, seq, var, insn; + unsigned i; + + if (VARRAY_ACTIVE_SIZE (ve->var_expansions) == 0) + return 1; + + start_sequence (); + if (ve->op == PLUS || ve->op == MINUS) + for (i = 0; i < VARRAY_ACTIVE_SIZE (ve->var_expansions); i++) + { + var = VARRAY_RTX (ve->var_expansions, i); + sum = simplify_gen_binary (PLUS, GET_MODE (ve->reg), + var, sum); + } + else if (ve->op == MULT) + for (i = 0; i < VARRAY_ACTIVE_SIZE (ve->var_expansions); i++) + { + var = VARRAY_RTX (ve->var_expansions, i); + sum = simplify_gen_binary (MULT, GET_MODE (ve->reg), + var, sum); + } + + expr = force_operand (sum, ve->reg); + if (expr != ve->reg) + emit_move_insn (ve->reg, expr); + seq = get_insns (); + end_sequence (); + + insn = BB_HEAD (place); + while (!NOTE_INSN_BASIC_BLOCK_P (insn)) + insn = NEXT_INSN (insn); + + emit_insn_after (seq, insn); + + /* Continue traversing the hash table. */ + return 1; + } + + /* Apply loop optimizations in loop copies using the + data which gathered during the unrolling. Structure + OPT_INFO record that data. + UNROLLING is true if we unrolled (not peeled) the loop. REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of the loop (as it should happen in complete unrolling, but not in ordinary peeling of the loop). */ static void ! apply_opt_in_copies (struct opt_info *opt_info, ! unsigned n_copies, bool unrolling, ! bool rewrite_original_loop) { unsigned i, delta; basic_block bb, orig_bb; rtx insn, orig_insn, next; struct iv_to_split ivts_templ, *ivts; ! struct var_to_expand ve_templ, *ves; ! /* Sanity check -- we need to put initialization in the original loop body. */ gcc_assert (!unrolling || rewrite_original_loop); ! /* Allocate the basic variables (i0). */ ! if (opt_info->insns_to_split) ! htab_traverse (opt_info->insns_to_split, allocate_basic_variable, NULL); ! ! for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++) { bb = BASIC_BLOCK (i); orig_bb = bb->rbi->original; ! delta = determine_split_iv_delta (bb->rbi->copy_number, n_copies, unrolling); orig_insn = BB_HEAD (orig_bb); for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next) ! { ! next = NEXT_INSN (insn); ! if (!INSN_P (insn)) ! continue; ! ! while (!INSN_P (orig_insn)) ! orig_insn = NEXT_INSN (orig_insn); ! ! ivts_templ.insn = orig_insn; ! ve_templ.insn = orig_insn; ! ! /* Apply splitting iv optimization. */ ! if (opt_info->insns_to_split) ! { ! ivts = htab_find (opt_info->insns_to_split, &ivts_templ); ! ! if (ivts) ! { ! #ifdef ENABLE_CHECKING ! if (!rtx_equal_p (PATTERN (insn), PATTERN (orig_insn))) ! abort (); #endif ! ! if (!delta) ! insert_base_initialization (ivts, insn); ! split_iv (ivts, insn, delta); ! } ! } ! /* Apply variable expansion optimization. */ ! if (unrolling && opt_info->insns_with_var_to_expand) ! { ! ves = htab_find (opt_info->insns_with_var_to_expand, &ve_templ); ! if (ves) ! { ! #ifdef ENABLE_CHECKING ! if (!rtx_equal_p (PATTERN (insn), PATTERN (orig_insn))) ! abort (); ! #endif ! expand_var_during_unrolling (ves, insn); ! } ! } ! orig_insn = NEXT_INSN (orig_insn); ! } } if (!rewrite_original_loop) return; ! ! /* Initialize the variable expansions in the loop preheader ! and take care of combining them at the loop exit. */ ! if (opt_info->insns_with_var_to_expand) ! { ! htab_traverse (opt_info->insns_with_var_to_expand, ! insert_var_expansion_initialization, ! opt_info->loop_preheader); ! htab_traverse (opt_info->insns_with_var_to_expand, ! combine_var_copies_in_loop_exit, ! opt_info->loop_exit); ! } ! /* Rewrite also the original loop body. Find them as originals of the blocks in the last copied iteration, i.e. those that have bb->rbi->original->copy == bb. */ ! for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++) { bb = BASIC_BLOCK (i); orig_bb = bb->rbi->original; if (orig_bb->rbi->copy != bb) continue; ! delta = determine_split_iv_delta (0, n_copies, unrolling); for (orig_insn = BB_HEAD (orig_bb); ! orig_insn != NEXT_INSN (BB_END (bb)); ! orig_insn = next) ! { ! next = NEXT_INSN (orig_insn); ! ! if (!INSN_P (orig_insn)) ! continue; ! ! ivts_templ.insn = orig_insn; ! if (opt_info->insns_to_split) ! { ! ivts = htab_find (opt_info->insns_to_split, &ivts_templ); ! if (ivts) ! { ! if (!delta) ! insert_base_initialization (ivts, orig_insn); ! split_iv (ivts, orig_insn, delta); ! continue; ! } ! } ! ! } ! } ! } ! /* Release the data structures used for the variable expansion ! optimization. Callbacks for htab_traverse. */ ! static int ! release_var_copies (void **slot, void *data ATTRIBUTE_UNUSED) ! { ! struct var_to_expand *ve = *slot; ! ! VARRAY_CLEAR (ve->var_expansions); ! ! /* Continue traversing the hash table. */ ! return 1; } ! /* Release OPT_INFO. */ static void ! free_opt_info (struct opt_info *opt_info) { ! if (opt_info->insns_to_split) ! htab_delete (opt_info->insns_to_split); ! if (opt_info->insns_with_var_to_expand) ! { ! htab_traverse (opt_info->insns_with_var_to_expand, ! release_var_copies, NULL); ! htab_delete (opt_info->insns_with_var_to_expand); ! } ! free (opt_info); } Index: params.def =================================================================== RCS file: /cvsroot/gcc/gcc/gcc/params.def,v retrieving revision 1.46 diff -c -3 -p -r1.46 params.def *** params.def 5 Sep 2004 09:25:26 -0000 1.46 --- params.def 28 Sep 2004 11:31:42 -0000 *************** DEFPARAM (PARAM_MAX_INLINE_INSNS_RTL, *** 95,100 **** --- 95,108 ---- "The maximum number of instructions for the RTL inliner", 600) + /* Limit the number of expansions created by the variable expansion + optimization to avoid register pressure. */ + DEFPARAM (PARAM_MAX_VARIABLE_EXPANSIONS, + "max-variable-expansions-in-unroller", + "Limit the number of expansions an accumulator can have when \ + expanding it in loop copies", + 1) + /* The maximum number of instructions to consider when looking for an instruction to fill a delay slot. If more than this arbitrary number of instructions is searched, the time savings from filling Index: params.h =================================================================== RCS file: /cvsroot/gcc/gcc/gcc/params.h,v retrieving revision 1.21 diff -c -3 -p -r1.21 params.h *** params.h 19 Aug 2004 10:35:54 -0000 1.21 --- params.h 28 Sep 2004 11:31:42 -0000 *************** typedef enum compiler_param *** 94,99 **** --- 94,101 ---- PARAM_VALUE (PARAM_MAX_INLINE_INSNS_AUTO) #define MAX_INLINE_INSNS_RTL \ PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RTL) + #define MAX_VARIABLE_EXPANSIONS \ + PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS) #define MAX_DELAY_SLOT_INSN_SEARCH \ PARAM_VALUE (PARAM_MAX_DELAY_SLOT_INSN_SEARCH) #define MAX_DELAY_SLOT_LIVE_SEARCH \ Index: doc/invoke.texi =================================================================== RCS file: /cvsroot/gcc/gcc/gcc/doc/invoke.texi,v retrieving revision 1.542 diff -c -3 -p -r1.542 invoke.texi *** doc/invoke.texi 24 Sep 2004 23:18:01 -0000 1.542 --- doc/invoke.texi 28 Sep 2004 11:31:49 -0000 *************** Objective-C and Objective-C++ Dialects}. *** 316,321 **** --- 316,322 ---- -fstrength-reduce -fstrict-aliasing -ftracer -fthread-jumps @gol -funroll-all-loops -funroll-loops -fpeel-loops @gol -fsplit-ivs-in-unroller -funswitch-loops @gol + -fvariable-expansion-in-unroller @gol -ftree-pre -ftree-ccp -ftree-dce -ftree-loop-optimize @gol -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol -ftree-dominator-opts -ftree-dse -ftree-copyrename @gol *************** on some of the architectures due to rest *** 4728,4733 **** --- 4729,4739 ---- This optimization is enabled by default. + @item -fvariable-expansion-in-unroller + @opindex -fvariable-expansion-in-unroller + With this option, the compiler will create multiple copies of some + local variables when unrolling a loop which can result in superior code. + @item -fprefetch-loop-arrays @opindex fprefetch-loop-arrays If supported by the target machine, generate instructions to prefetch