CbC/CbC_gcc: gcc/loop-unroll.c comparison

comparison gcc/loop-unroll.c @ 55:77e2b8dfacca gcc-4.4.5

update it from 4.4.3 to 4.5.0

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Fri, 12 Feb 2010 23:39:51 +0900
parents	a06113de4d67
children	b7f97abdc517

comparison

equal deleted inserted replaced

-:c156f1bd5cd9
+:77e2b8dfacca
 #include "cfglayout.h"
 #include "params.h"
 #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
 the impact on performance is greatest here, and we want to avoid
 unnecessary code size growth.  The gain is caused by greater sequentiality
 {
 rtx insn;		/* The insn in that the induction variable occurs.  */
 rtx base_var;		/* The variable on that the values in the further
 			   iterations are based.  */
 rtx step;		/* Step of the induction variable.  */
+struct iv_to_split *next; /* Next entry in walking order.  */
 unsigned n_loc;
 unsigned loc[3];	/* Location where the definition of the induction
 			   variable occurs in the insn.  For example if
 			   N_LOC is 2, the expression is located at
 			   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.  */
 VEC(rtx,heap) *var_expansions;   /* The copies of the accumulator which is expanded.  */
-enum rtx_code op;                /* The type of the accumulation - addition, subtraction
+struct var_to_expand *next;	   /* Next entry in walking order.  */
+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 reuse_expansion;             /* The expansion we intend to reuse to expand
 the accumulator.  If REUSE_EXPANSION is 0 reuse
 the original accumulator.  Else use
 var_expansions[REUSE_EXPANSION - 1].  */
 unsigned accum_pos;              /* The position in which the accumulator is placed in
 the insn src.  For example in x = x + something
 accum_pos is 0 while in x = something + x accum_pos
 is 1.  */
 the unrolled loop.  */
 struct opt_info
 {
 htab_t insns_to_split;           /* A hashtable of insns to split.  */
+struct iv_to_split *iv_to_split_head; /* The first iv to split.  */
+struct iv_to_split **iv_to_split_tail; /* Pointer to the tail of the list.  */
 htab_t insns_with_var_to_expand; /* A hashtable of insns with accumulators
 to expand.  */
+struct var_to_expand *var_to_expand_head; /* The first var to expand.  */
+struct var_to_expand **var_to_expand_tail; /* Pointer to the tail of the list.  */
 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 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 void insert_var_expansion_initialization (struct var_to_expand *,
-static int combine_var_copies_in_loop_exit (void **, void *);
+						 basic_block);
-static int release_var_copies (void **, void *);
+static void combine_var_copies_in_loop_exit (struct var_to_expand *,
+					     basic_block);
 static rtx get_expansion (struct var_to_expand *);
 /* Unroll and/or peel (depending on FLAGS) LOOPS.  */
 void
 unroll_and_peel_loops (int flags)
 unsigned i;
 VEC (edge, heap) *remove_edges;
 edge ein;
 struct niter_desc *desc = get_simple_loop_desc (loop);
 struct opt_info *opt_info = NULL;
 npeel = desc->niter;
 if (npeel)
 {
 bool ok;
 wont_exit = sbitmap_alloc (npeel + 1);
 sbitmap_ones (wont_exit);
 RESET_BIT (wont_exit, 0);
 if (desc->noloop_assumptions)
 	RESET_BIT (wont_exit, 1);
 remove_edges = NULL;
 if (flag_split_ivs_in_unroller)
 opt_info = analyze_insns_in_loop (loop);
 opt_info_start_duplication (opt_info);
 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 					  npeel,
 					  wont_exit, desc->out_edge,
 					  &remove_edges,
 					  | (opt_info
 					     ? DLTHE_RECORD_COPY_NUMBER : 0));
 gcc_assert (ok);
 free (wont_exit);
 if (opt_info)
 	{
 	  apply_opt_in_copies (opt_info, npeel, false, true);
 	  free_opt_info (opt_info);
 	}
 fprintf (dump_file, ";; max_unroll %d (%d copies, initial %d).\n",
 	     best_unroll + 1, best_copies, nunroll);
 loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
 loop->lpt_decision.times = best_unroll;
 if (dump_file)
 fprintf (dump_file,
 	     ";; Decided to unroll the constant times rolling loop, %d times.\n",
 	     loop->lpt_decision.times);
 }
 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;
 bool ok;
 niter = desc->niter;
 /* Should not get here (such loop should be peeled instead).  */
 gcc_assert (niter > max_unroll + 1);
 wont_exit = sbitmap_alloc (max_unroll + 1);
 sbitmap_ones (wont_exit);
 remove_edges = NULL;
 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
 	 in the first copy, so that the loops that start with test
 	 of exit condition have continuous body after unrolling.  */
 						 ? DLTHE_RECORD_COPY_NUMBER
 						   : 0));
 	  gcc_assert (ok);
 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;
 	}
 	  || desc->noloop_assumptions)
 	{
 	  RESET_BIT (wont_exit, 0);
 	  if (desc->noloop_assumptions)
 	    RESET_BIT (wont_exit, 1);
 opt_info_start_duplication (opt_info);
 	  ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 					      exit_mod + 1,
 					      wont_exit, desc->out_edge,
 					      &remove_edges,
 					      DLTHE_FLAG_UPDATE_FREQ
 					      | (opt_info && exit_mod > 0
 						 ? DLTHE_RECORD_COPY_NUMBER
 						   : 0));
 	  gcc_assert (ok);
 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;
 RESET_BIT (wont_exit, max_unroll);
 }
 /* Now unroll the loop.  */
 opt_info_start_duplication (opt_info);
 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
 				      max_unroll,
 				      wont_exit, desc->out_edge,
 				      &remove_edges,
 if (exit_at_end)
 {
 basic_block exit_block = get_bb_copy (desc->in_edge->src);
 /* Find a new in and out edge; they are in the last copy we have made.  */
 if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
 	{
 	  desc->out_edge = EDGE_SUCC (exit_block, 0);
 	  desc->in_edge = EDGE_SUCC (exit_block, 1);
 	}
 for (i = 1; 2 * i <= nunroll; i *= 2)
 continue;
 loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
 loop->lpt_decision.times = i - 1;
 if (dump_file)
 fprintf (dump_file,
 	     ";; Decided to unroll the runtime computable "
 	     "times rolling loop, %d times.\n",
 	     loop->lpt_decision.times);
 {
 basic_block bb;
 if (!insns)
 return NULL;
 bb = split_edge (e);
 emit_insn_after (insns, BB_END (bb));
 /* ??? We used to assume that INSNS can contain control flow insns, and
 that we had to try to find sub basic blocks in BB to maintain a valid
 CFG.  For this purpose we used to set the BB_SUPERBLOCK flag on BB
 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;
 bool ok;
 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 = NULL;
 body = get_loop_body (loop);
 for (i = 0; i < loop->num_nodes; i++)
 /* And unroll loop.  */
 sbitmap_ones (wont_exit);
 RESET_BIT (wont_exit, may_exit_copy);
 opt_info_start_duplication (opt_info);
 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
 				      max_unroll,
 				      wont_exit, desc->out_edge,
 				      &remove_edges,
 				      DLTHE_FLAG_UPDATE_FREQ
 				      | (opt_info
 					 ? DLTHE_RECORD_COPY_NUMBER
 					   : 0));
 gcc_assert (ok);
 if (opt_info)
 {
 apply_opt_in_copies (opt_info, max_unroll, true, true);
 free_opt_info (opt_info);
 }
 if (exit_at_end)
 {
 basic_block exit_block = get_bb_copy (desc->in_edge->src);
 /* Find a new in and out edge; they are in the last copy we have
 	 made.  */
 if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
 	{
 	  desc->out_edge = EDGE_SUCC (exit_block, 0);
 	  desc->in_edge = EDGE_SUCC (exit_block, 1);
 	}
 }
 /* Success.  */
 loop->lpt_decision.decision = LPT_PEEL_SIMPLE;
 loop->lpt_decision.times = npeel;
 if (dump_file)
 fprintf (dump_file, ";; Decided to simply peel the loop, %d times.\n",
 	     loop->lpt_decision.times);
 }
 sbitmap wont_exit;
 unsigned npeel = loop->lpt_decision.times;
 struct niter_desc *desc = get_simple_loop_desc (loop);
 struct opt_info *opt_info = NULL;
 bool ok;
 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);
 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 				      npeel, wont_exit, NULL,
 				      NULL, DLTHE_FLAG_UPDATE_FREQ
 				      | (opt_info
 					 ? DLTHE_RECORD_COPY_NUMBER
 					   : 0));
 gcc_assert (ok);
 free (wont_exit);
 if (opt_info)
 {
 apply_opt_in_copies (opt_info, npeel, false, false);
 free_opt_info (opt_info);
 }
 for (i = 1; 2 * i <= nunroll; i *= 2)
 continue;
 loop->lpt_decision.decision = LPT_UNROLL_STUPID;
 loop->lpt_decision.times = i - 1;
 if (dump_file)
 fprintf (dump_file,
 	     ";; Decided to unroll the loop stupidly, %d times.\n",
 	     loop->lpt_decision.times);
 }
 sbitmap wont_exit;
 unsigned nunroll = loop->lpt_decision.times;
 struct niter_desc *desc = get_simple_loop_desc (loop);
 struct opt_info *opt_info = NULL;
 bool ok;
 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);
 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
 				      nunroll, wont_exit,
 				      NULL, NULL,
 				      DLTHE_FLAG_UPDATE_FREQ
 				      | (opt_info
 					 ? DLTHE_RECORD_COPY_NUMBER
 					   : 0));
 gcc_assert (ok);
 if (opt_info)
 {
 apply_opt_in_copies (opt_info, nunroll, true, true);
 free_opt_info (opt_info);
 }
 ve_info_hash (const void *ves)
 {
 return (hashval_t) INSN_UID (((const struct var_to_expand *) ves)->insn);
 }
 /* Return true if IVTS1 and IVTS2 (which are really both of type
 "var_to_expand *") refer to the same instruction.  */
 static int
 ve_info_eq (const void *ivts1, const void *ivts2)
 {
 const struct var_to_expand *const i1 = (const struct var_to_expand *) ivts1;
 const struct var_to_expand *const i2 = (const struct var_to_expand *) ivts2;
 return i1->insn == i2->insn;
 }
 /* Returns true if REG is referenced in one insn in LOOP.  */
 {
 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)
 unsigned accum_pos;
 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 (!have_insn_for (GET_CODE (src), GET_MODE (src)))
 return NULL;
 op1 = XEXP (src, 0);
 op2 = XEXP (src, 1);
 if (!REG_P (dest)
 && !(GET_CODE (dest) == SUBREG
 && REG_P (SUBREG_REG (dest))))
 return NULL;
 if (rtx_equal_p (dest, op1))
 accum_pos = 0;
 else if (rtx_equal_p (dest, op2))
 accum_pos = 1;
 else
 /* The method of expansion that we are using; which includes
 the initialization of the expansions with zero and the summation of
 the expansions at the end of the computation will yield wrong results
 for (x = something - x) thus avoid using it in that case.  */
 if (accum_pos == 1
 && GET_CODE (src) == MINUS)
 return NULL;
 something = (accum_pos == 0)? op2 : op1;
 if (!referenced_in_one_insn_in_loop_p (loop, dest))
 return NULL;
 if (rtx_referenced_p (dest, something))
 return NULL;
 mode1 = GET_MODE (dest);
 mode2 = GET_MODE (something);
 if ((FLOAT_MODE_P (mode1)
 || FLOAT_MODE_P (mode2))
 && !flag_associative_math)
 return NULL;
 if (dump_file)
 {
 fprintf (dump_file,
 }
 /* Record the accumulator to expand.  */
 ves = XNEW (struct var_to_expand);
 ves->insn = insn;
+ves->reg = copy_rtx (dest);
 ves->var_expansions = VEC_alloc (rtx, heap, 1);
-ves->reg = copy_rtx (dest);
+ves->next = NULL;
 ves->op = GET_CODE (src);
 ves->expansion_count = 0;
 ves->reuse_expansion = 0;
 ves->accum_pos = accum_pos;
 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 = 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)
 /* Record the insn to split.  */
 ivts = XNEW (struct iv_to_split);
 ivts->insn = insn;
 ivts->base_var = NULL_RTX;
 ivts->step = iv.step;
+ivts->next = NULL;
 ivts->n_loc = 1;
 ivts->loc[0] = 1;
 return ivts;
 }
 /* Determines which of insns in LOOP can be optimized.
 Return a OPT_INFO struct with the relevant hash tables filled
 PTR *slot1;
 PTR *slot2;
 VEC (edge, heap) *edges = get_loop_exit_edges (loop);
 edge exit;
 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);
+opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
+					      si_info_hash, si_info_eq, free);
+opt_info->iv_to_split_head = NULL;
+opt_info->iv_to_split_tail = &opt_info->iv_to_split_head;
+}
 /* Record the loop exit bb and loop preheader before the unrolling.  */
 opt_info->loop_preheader = loop_preheader_edge (loop)->src;
 if (VEC_length (edge, edges) == 1)
 {
 exit = VEC_index (edge, edges, 0);
 if (!(exit->flags & EDGE_COMPLEX))
 	{
 	  opt_info->loop_exit = split_edge (exit);
 	  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);
+opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
+							ve_info_hash,
+							ve_info_eq, free);
+opt_info->var_to_expand_head = NULL;
+opt_info->var_to_expand_tail = &opt_info->var_to_expand_head;
+}
 for (i = 0; i < loop->num_nodes; i++)
 {
 bb = body[i];
 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
 	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);
+	    gcc_assert (*slot1 == NULL);
 *slot1 = ivts;
+	    *opt_info->iv_to_split_tail = ivts;
+	    opt_info->iv_to_split_tail = &ivts->next;
 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);
+	    gcc_assert (*slot2 == NULL);
 *slot2 = ves;
+	    *opt_info->var_to_expand_tail = ves;
+	    opt_info->var_to_expand_tail = &ves->next;
 }
 }
 }
 VEC_free (edge, heap, 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;
 }
 ret = &XEXP (*ret, ivts->loc[i]);
 return ret;
 }
-/* Allocate basic variable for the induction variable chain.  Callback for
+/* Allocate basic variable for the induction variable chain.  */
-htab_traverse.  */
+static void
-static int
+allocate_basic_variable (struct iv_to_split *ivts)
-allocate_basic_variable (void **slot, void *data ATTRIBUTE_UNUSED)
+{
-{
-struct iv_to_split *ivts = (struct iv_to_split *) *slot;
 rtx expr = *get_ivts_expr (single_set (ivts->insn), ivts);
 ivts->base_var = gen_reg_rtx (GET_MODE (expr));
-return 1;
 }
 /* Insert initialization of basic variable of IVTS before INSN, taking
 the initial value from INSN.  */
 if (expr != var)
 emit_move_insn (var, expr);
 seq = get_insns ();
 end_sequence ();
 emit_insn_before (seq, insn);
 if (validate_change (insn, loc, var, 0))
 return;
 /* The last chance.  Try recreating the assignment in insn
 completely from scratch.  */
 src = force_operand (src, dest);
 if (src != dest)
 emit_move_insn (dest, src);
 seq = get_insns ();
 end_sequence ();
 emit_insn_before (seq, insn);
 delete_insn (insn);
 }
 static rtx
 get_expansion (struct var_to_expand *ve)
 {
 rtx reg;
 if (ve->reuse_expansion == 0)
 reg = ve->reg;
 else
 reg = VEC_index (rtx, ve->var_expansions, ve->reuse_expansion - 1);
 if (VEC_length (rtx, ve->var_expansions) == (unsigned) ve->reuse_expansion)
 ve->reuse_expansion = 0;
 else
 ve->reuse_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);
 gcc_assert (set);
 /* 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;
 else
 new_reg = get_expansion (ve);
 validate_change (insn, &SET_DEST (set), new_reg, 1);
 validate_change (insn, &XEXP (SET_SRC (set), ve->accum_pos), new_reg, 1);
 if (apply_change_group ())
 if (really_new_expansion)
 {
 VEC_safe_push (rtx, heap, ve->var_expansions, new_reg);
 ve->expansion_count++;
 }
 }
-/* Initialize the variable expansions in loop preheader.
+/* Initialize the variable expansions in loop preheader.  PLACE is the
-Callbacks for htab_traverse.  PLACE_P is the loop-preheader
+loop-preheader basic block where the initialization of the
-basic block where the initialization of the expansions
+expansions should take place.  The expansions are initialized with
-should take place.  The expansions are initialized with (-0)
+(-0) when the operation is plus or minus to honor sign zero.  This
-when the operation is plus or minus to honor sign zero.
+way we can prevent cases where the sign of the final result is
-This way we can prevent cases where the sign of the final result is
+effected by the sign of the expansion.  Here is an example to
-effected by the sign of the expansion.
+demonstrate this:
-Here is an example to demonstrate this:
 for (i = 0 ; i < n; i++)
 sum += something;
 ==>
 sum1 += something
 ....
 i = i+1
 sum2 += something;
 ....
 When SUM is initialized with -zero and SOMETHING is also -zero; the
 final result of sum should be -zero thus the expansions sum1 and sum2
 should be initialized with -zero as well (otherwise we will get +zero
 as the final result).  */
-static int
+static void
-insert_var_expansion_initialization (void **slot, void *place_p)
+insert_var_expansion_initialization (struct var_to_expand *ve,
-{
+				     basic_block place)
-struct var_to_expand *ve = (struct var_to_expand *) *slot;
+{
-basic_block place = (basic_block)place_p;
 rtx seq, var, zero_init, insn;
 unsigned i;
 enum machine_mode mode = GET_MODE (ve->reg);
 bool honor_signed_zero_p = HONOR_SIGNED_ZEROS (mode);
 if (VEC_length (rtx, ve->var_expansions) == 0)
-return 1;
+return;
 start_sequence ();
 if (ve->op == PLUS || ve->op == MINUS)
 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
 {
 	if (honor_signed_zero_p)
 	  zero_init = simplify_gen_unary (NEG, mode, CONST0_RTX (mode), mode);
 	else
 	  zero_init = CONST0_RTX (mode);
 emit_move_insn (var, zero_init);
 }
 else if (ve->op == MULT)
 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); 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.  PLACE is the
+loop exit basic block where the summation of the expansions should
-/*  Combine the variable expansions at the loop exit.
+take place.  */
-Callbacks for htab_traverse.  PLACE_P is the loop exit
-basic block where the summation of the expansions should
+static void
-take place.  */
+combine_var_copies_in_loop_exit (struct var_to_expand *ve, basic_block place)
+{
-static int
-combine_var_copies_in_loop_exit (void **slot, void *place_p)
-{
-struct var_to_expand *ve = (struct var_to_expand *) *slot;
-basic_block place = (basic_block)place_p;
 rtx sum = ve->reg;
 rtx expr, seq, var, insn;
 unsigned i;
 if (VEC_length (rtx, ve->var_expansions) == 0)
-return 1;
+return;
 start_sequence ();
 if (ve->op == PLUS || ve->op == MINUS)
 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
 {
 sum = simplify_gen_binary (PLUS, GET_MODE (ve->reg),
 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); 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
-/* 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 (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
+allocate_basic_variable (ivts);
 for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
 {
 bb = BASIC_BLOCK (i);
 orig_bb = get_bb_original (bb);
 /* bb->aux holds position in copy sequence initialized by
 	 duplicate_loop_to_header_edge.  */
 delta = determine_split_iv_delta ((size_t)bb->aux, n_copies,
 					unrolling);
 bb->aux = 0;
 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 = (struct iv_to_split *)
 		htab_find (opt_info->insns_to_split, &ivts_templ);
 if (ivts)
 {
 		  gcc_assert (GET_CODE (PATTERN (insn))
 			      == GET_CODE (PATTERN (orig_insn)));
 if (!delta)
 insert_base_initialization (ivts, insn);
 split_iv (ivts, insn, delta);
 }
 }
 if (unrolling && opt_info->insns_with_var_to_expand)
 {
 ves = (struct var_to_expand *)
 		htab_find (opt_info->insns_with_var_to_expand, &ve_templ);
 if (ves)
 {
 		  gcc_assert (GET_CODE (PATTERN (insn))
 			      == GET_CODE (PATTERN (orig_insn)));
 expand_var_during_unrolling (ves, 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,
+for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
-insert_var_expansion_initialization,
+	insert_var_expansion_initialization (ves, opt_info->loop_preheader);
-opt_info->loop_preheader);
+for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
-htab_traverse (opt_info->insns_with_var_to_expand,
+	combine_var_copies_in_loop_exit (ves, opt_info->loop_exit);
-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
 get_bb_copy (get_bb_original (bb)) == bb.  */
 for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
 {
 bb = BASIC_BLOCK (i);
 orig_bb = get_bb_original (bb);
 if (get_bb_copy (orig_bb) != 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 = (struct iv_to_split *)
 		htab_find (opt_info->insns_to_split, &ivts_templ);
 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 = (struct var_to_expand *) *slot;
-VEC_free (rtx, heap, ve->var_expansions);
-/* Continue traversing the hash table.  */
-return 1;
 }
 /* Release OPT_INFO.  */
 static void
 {
 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,
+struct var_to_expand *ves;
-release_var_copies, NULL);
+for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
+	VEC_free (rtx, heap, ves->var_expansions);
 htab_delete (opt_info->insns_with_var_to_expand);
 }
 free (opt_info);
 }

Mercurial > hg > CbC > CbC_gcc

comparison gcc/loop-unroll.c @ 55:77e2b8dfacca gcc-4.4.5