This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] Some bugfixes
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 28 Feb 2004 00:12:59 +0100
- Subject: [lno] Some bugfixes
Hello,
this patch fixes several problems in the new loop optimizer
(some bugs, corrects the estimation of register pressure by also
taking invariants that are necessary to preserve into account).
It also prevents from creating induction variables incremented at the
start of the loop body, that used to be split into two ivs by dominator
optimization, thus creating an unnecessary register pressure.
It causes some compile time regressions, I will fix this tomorrow.
Zdenek
Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.64
diff -c -3 -p -r1.1.2.64 ChangeLog.lno
*** ChangeLog.lno 27 Feb 2004 00:46:22 -0000 1.1.2.64
--- ChangeLog.lno 27 Feb 2004 23:06:40 -0000
***************
*** 1,5 ****
--- 1,51 ----
2004-02-27 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
+ * tree-cfg.c (cleanup_control_expr_graph): Prevent probability from
+ overflowing.
+ * loop-invariant.c (get_current_def): Fix.
+ * tree-ssa-loop-im.c (move_computations): Only call rewrite_into_ssa
+ if vars_to_rename is nonempty.
+ * tree-ssa-loop-ivopts.c (outermost_usage, ivs): Removed.
+ (struct version_info): New.
+ (version_info, max_inv_id): New variables.
+ (struct cost_pair): Added depends_on field.
+ (struct iv_use): Removed fields choices, n_choices, min_cost and
+ min_cost_cand.
+ (enum iv_position, dump_cand, ip_end_pos, add_candidate_1,
+ determine_iv_cost, create_new_iv): IP_START position disabled.
+ (find_optimal_iv_set_1, min_remaining_cost, undo_changes,
+ execute_removal, add_forbidden_ivs, try_candidate): Removed.
+ (dump_use): Do not dump removed fields.
+ (ver_info, name_info, update_outermost_usage, record_invariant,
+ find_invariants_stmt, find_depends, try_improve_iv_set): New functions.
+ (find_outermost_usage): Handle uses in phis.
+ (divide): Update comment.
+ (tree_ssa_iv_optimize_init): Initialize version_info instead of ivs
+ and outermost_usage.
+ (set_iv, get_iv, find_induction_variables, add_old_ivs_candidates):
+ Use version_info instead of ivs.
+ (record_use): Do not initialize removed fields.
+ (find_interesting_uses_op): Call record_use.
+ (find_interesting_uses_stmt): Call find_invariants_stmt.
+ (find_interesting_uses): Scan just the current loop.
+ (set_use_iv_cost): Initialize depends_on field.
+ (get_use_iv_cost): Return depends_on field.
+ (get_computation): Handle special cases.
+ (force_var_cost, split_address_cost, ptr_difference_cost,
+ difference_cost, get_computation_cost, determine_use_iv_cost_generic,
+ determine_use_iv_cost_address, determine_use_iv_cost_condition):
+ Determine depends_on bitmap.
+ (determine_use_iv_costs): Dump depends_on bitmap.
+ (init_set_costs): Use information about invariants.
+ (find_best_candidate, set_cost, get_initial_solution,
+ find_optimal_iv_set): Take depends_on into account.
+ (rewrite_uses): Use use->selected to select candidate.
+ (free_loop_data, tree_ssa_iv_optimize_finalize): Cleanup version_info
+ instead of ivs. Free depends_on bitmaps.
+ (tree_ssa_iv_optimize_loop): Do not pass iv_set to rewrite_uses.
+
+ 2004-02-27 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
+
* cfgloopmanip.c (loopify): Fix comment.
* loop-iv.c (lowpart_byte, lowpart_subreg_p): Removed.
(lowpart_subreg, simple_reg_p, iv_get_reaching_def, get_biv_step_1,
Index: loop-invariant.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/loop-invariant.c,v
retrieving revision 1.1.4.1
diff -c -3 -p -r1.1.4.1 loop-invariant.c
*** loop-invariant.c 19 Feb 2004 07:14:42 -0000 1.1.4.1
--- loop-invariant.c 27 Feb 2004 23:06:40 -0000
*************** get_current_def (rtx reg, rtx insn, stru
*** 568,579 ****
if (!(*def)->simple_p)
return false;
if (!(*def)->reg_next)
return true;
/* Check that the use dominates the next definition. This ensures that
it indeed must be reached by the actual one. */
- bb = BLOCK_FOR_INSN (insn);
if (!dominated_by_p (CDI_DOMINATORS, (*def)->reg_next->bb, bb))
return false;
--- 568,582 ----
if (!(*def)->simple_p)
return false;
+ bb = BLOCK_FOR_INSN (insn);
+ if (!dominated_by_p (CDI_DOMINATORS, bb, (*def)->bb))
+ return false;
+
if (!(*def)->reg_next)
return true;
/* Check that the use dominates the next definition. This ensures that
it indeed must be reached by the actual one. */
if (!dominated_by_p (CDI_DOMINATORS, (*def)->reg_next->bb, bb))
return false;
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.244.2.8
diff -c -3 -p -r1.1.4.244.2.8 tree-cfg.c
*** tree-cfg.c 21 Feb 2004 23:10:01 -0000 1.1.4.244.2.8
--- tree-cfg.c 27 Feb 2004 23:06:40 -0000
*************** cleanup_control_expr_graph (basic_block
*** 1806,1811 ****
--- 1806,1814 ----
ssa_remove_edge (e);
retval = true;
}
+
+ if (taken_edge->probability > REG_BR_PROB_BASE)
+ taken_edge->probability = REG_BR_PROB_BASE;
}
}
else
Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-im.c,v
retrieving revision 1.1.2.4
diff -c -3 -p -r1.1.2.4 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c 24 Feb 2004 23:52:28 -0000 1.1.2.4
--- tree-ssa-loop-im.c 27 Feb 2004 23:06:40 -0000
*************** move_computations (void)
*** 555,561 ****
fini_walk_dominator_tree (&walk_data);
commit_inserts ();
! rewrite_into_ssa ();
BITMAP_XFREE (vars_to_rename);
}
--- 555,562 ----
fini_walk_dominator_tree (&walk_data);
commit_inserts ();
! if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa ();
BITMAP_XFREE (vars_to_rename);
}
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 24 Feb 2004 23:52:28 -0000 1.1.2.10
--- tree-ssa-loop-ivopts.c 27 Feb 2004 23:06:40 -0000
*************** static struct loop *current_loop;
*** 109,120 ****
/* The highest ssa name before optimizations. */
static unsigned old_highest_ssa_version;
! /* The outermost loop in that the variable is used. */
! static struct loop **outermost_usage;
! /* The array of induction variable descriptions, indexed by the ssa name
! version. */
! static struct iv **ivs;
/* Information attached to loop. */
struct loop_data
--- 109,131 ----
/* The highest ssa name before optimizations. */
static unsigned old_highest_ssa_version;
! /* Per-ssa version information (induction variable descriptions, etc.). */
! struct version_info
! {
! tree name; /* The ssa name. */
! struct iv *iv; /* Induction variable description. */
! bool has_nonlin_use; /* For a loop-level invariant, whether it is used in
! an expression that is not an induction variable. */
! unsigned inv_id; /* Id of an invariant. */
! struct loop *outermost_usage;
! /* The outermost loop in that the variable is used. */
! };
!
! /* The array of this information indexed by the ssa name version. */
! static struct version_info *version_info;
! /* The maximum invariant id. */
! static unsigned max_inv_id;
/* Information attached to loop. */
struct loop_data
*************** struct cost_pair
*** 145,150 ****
--- 156,163 ----
{
struct iv_cand *cand; /* The candidate. */
unsigned cost; /* The cost. */
+ bitmap depends_on; /* The list of invariants that have to be
+ preserved. */
};
/* Use. */
*************** struct iv_use
*** 157,182 ****
tree *op_p; /* The place where it occurs. */
bitmap related_cands; /* The set of "related" iv candidates. */
- bitmap choices; /* The set of available candidates. */
- unsigned n_choices; /* And its size. */
- unsigned min_cost; /* The minimal cost among choices. */
- struct iv_cand *min_cost_cand;
- /* And the corresponding candidate. */
-
- struct iv_cand *selected;
- /* The candidate selected for the use. */
unsigned n_map_members; /* Number of candidates in the cost_map list. */
struct cost_pair *cost_map;
/* The costs wrto the iv candidates. */
};
/* The uses of induction variables. */
static varray_type iv_uses;
/* The position where the iv is computed. */
enum iv_position
{
IP_START, /* At the very beginning of the loop body. */
IP_NORMAL, /* At the end, just before the exit condition. */
IP_END /* At the end of the latch block. */
};
--- 170,196 ----
tree *op_p; /* The place where it occurs. */
bitmap related_cands; /* The set of "related" iv candidates. */
unsigned n_map_members; /* Number of candidates in the cost_map list. */
struct cost_pair *cost_map;
/* The costs wrto the iv candidates. */
+
+ struct iv_cand *selected;
+ /* The selected candidate. */
};
/* The uses of induction variables. */
static varray_type iv_uses;
+ /* Disabled -- the dominator optimizations tend to reuse the value from
+ the previous iteration, which increases register pressure. */
+ #define DISABLE_IP_START 0
+
/* The position where the iv is computed. */
enum iv_position
{
+ #if DISABLE_IP_START
IP_START, /* At the very beginning of the loop body. */
+ #endif
IP_NORMAL, /* At the end, just before the exit condition. */
IP_END /* At the end of the latch block. */
};
*************** static varray_type decl_rtl_to_reset;
*** 222,229 ****
#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
static tree force_gimple_operand (tree, tree *, tree, bool);
- static void find_optimal_iv_set_1 (unsigned, unsigned, bitmap, unsigned,
- unsigned, bitmap, unsigned *);
/* Dumps information about the induction variable IV to FILE. */
--- 236,241 ----
*************** dump_use (FILE *file, struct iv_use *use
*** 308,329 ****
fprintf (file, " related candidates ");
dump_bitmap (file, use->related_cands);
-
- fprintf (file, " %d choices ", use->n_choices);
- dump_bitmap (file, use->choices);
-
- if (use->min_cost_cand)
- {
- fprintf (file, " best candidate %d (cost %d)",
- use->min_cost_cand->id, use->min_cost);
- fprintf (file, "\n");
- }
-
- if (use->selected)
- {
- fprintf (file, " selected candidate %d", use->selected->id);
- fprintf (file, "\n");
- }
}
/* Dumps information about the uses to FILE. */
--- 320,325 ----
*************** dump_cand (FILE *file, struct iv_cand *c
*** 357,365 ****
--- 353,363 ----
switch (cand->pos)
{
+ #if DISABLE_IP_START
case IP_START:
fprintf (file, " incremented at start\n");
break;
+ #endif
case IP_NORMAL:
fprintf (file, " incremented before exit test\n");
*************** dump_cand (FILE *file, struct iv_cand *c
*** 388,393 ****
--- 386,407 ----
}
}
+ /* Returns the info for ssa version VER. */
+
+ static inline struct version_info *
+ ver_info (unsigned ver)
+ {
+ return version_info + ver;
+ }
+
+ /* Returns the info for ssa name NAME. */
+
+ static inline struct version_info *
+ name_info (tree name)
+ {
+ return ver_info (SSA_NAME_VERSION (name));
+ }
+
/* Checks whether ARG is either NULL_TREE or constant zero. */
static bool
*************** divide (unsigned bits, unsigned HOST_WID
*** 483,489 ****
return false;
}
! /* Find the inverse of b. We compute it as b^2^(bits - 1) - 1 (mod 2^bits). */
inv = 1;
ex = b;
for (i = 0; i < bits - 1; i++)
--- 497,504 ----
return false;
}
! /* Find the inverse of b. We compute it as
! b^(2^(bits - 1) - 1) (mod 2^bits). */
inv = 1;
ex = b;
for (i = 0; i < bits - 1; i++)
*************** find_exit_edges (void)
*** 745,750 ****
--- 760,783 ----
}
}
+ /* Update usage information about OP using the fact that it is used in
+ the LOOP. */
+
+ static void
+ update_outermost_usage (tree op, struct loop *loop)
+ {
+ struct version_info *info;
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return;
+ info = name_info (op);
+
+ if (!info->outermost_usage)
+ info->outermost_usage = loop;
+ else
+ info->outermost_usage = find_common_loop (loop, info->outermost_usage);
+ }
+
/* Finds the outermost loop in that each ssa name is used. */
static void
*************** find_outermost_usage (void)
*** 752,766 ****
{
basic_block bb;
block_stmt_iterator bsi;
! unsigned i, ver;
use_optype uses;
! tree use, stmt;
! struct loop *loop;
FOR_EACH_BB (bb)
{
loop = bb->loop_father;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
--- 785,814 ----
{
basic_block bb;
block_stmt_iterator bsi;
! unsigned i;
use_optype uses;
! tree use, stmt, phi;
! struct loop *loop, *aloop;
FOR_EACH_BB (bb)
{
loop = bb->loop_father;
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ {
+ use = PHI_ARG_DEF (phi, i);
+
+ /* Use on the entry edge of a loop counts as use in the
+ superloop. */
+ if (loop->header == bb
+ && PHI_ARG_EDGE (phi, i) == loop_preheader_edge (loop))
+ aloop = loop->outer;
+ else
+ aloop = loop;
+ update_outermost_usage (use, aloop);
+ }
+
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
*************** find_outermost_usage (void)
*** 770,782 ****
for (i = 0; i < NUM_USES (uses); i++)
{
use = USE_OP (uses, i);
! ver = SSA_NAME_VERSION (use);
!
! if (!outermost_usage[ver])
! outermost_usage[ver] = loop;
! else
! outermost_usage[ver] = find_common_loop (loop,
! outermost_usage[ver]);
}
}
}
--- 818,824 ----
for (i = 0; i < NUM_USES (uses); i++)
{
use = USE_OP (uses, i);
! update_outermost_usage (use, loop);
}
}
}
*************** ip_end_pos (void)
*** 793,802 ****
--- 835,846 ----
bb = current_loop->latch;
last = last_stmt (bb);
+ #if DISABLE_IP_START
/* If the latch is empty, preserve this (inserting the latch block might need
extra jumps, which might spoil the code). */
if (!last || TREE_CODE (last) == LABEL_EXPR)
return NULL;
+ #endif
return bb;
}
*************** tree_ssa_iv_optimize_init (struct loops
*** 850,857 ****
unsigned i;
old_highest_ssa_version = highest_ssa_version;
! ivs = xcalloc (highest_ssa_version, sizeof (struct iv *));
! outermost_usage = xcalloc (highest_ssa_version, sizeof (struct loop *));
for (i = 1; i < loops->num; i++)
if (loops->parray[i])
--- 894,900 ----
unsigned i;
old_highest_ssa_version = highest_ssa_version;
! version_info = xcalloc (highest_ssa_version, sizeof (struct version_info));
for (i = 1; i < loops->num; i++)
if (loops->parray[i])
*************** alloc_iv (tree base, tree step)
*** 890,902 ****
static void
set_iv (tree iv, tree base, tree step)
{
! unsigned ver = SSA_NAME_VERSION (iv);
! if (ivs[ver])
abort ();
! ivs[ver] = alloc_iv (base, step);
! ivs[ver]->ssa_name = iv;
}
/* Finds induction variable declaration for VAR. */
--- 933,945 ----
static void
set_iv (tree iv, tree base, tree step)
{
! struct version_info *info = name_info (iv);
! if (info->iv)
abort ();
! info->iv = alloc_iv (base, step);
! info->iv->ssa_name = iv;
}
/* Finds induction variable declaration for VAR. */
*************** set_iv (tree iv, tree base, tree step)
*** 904,913 ****
static struct iv *
get_iv (tree var)
{
- unsigned ver = SSA_NAME_VERSION (var);
basic_block bb;
! if (!ivs[ver])
{
bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
--- 947,955 ----
static struct iv *
get_iv (tree var)
{
basic_block bb;
! if (!name_info (var)->iv)
{
bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
*************** get_iv (tree var)
*** 916,922 ****
set_iv (var, var, NULL_TREE);
}
! return ivs[ver];
}
/* Determines the step of a biv defined in PHI. */
--- 958,964 ----
set_iv (var, var, NULL_TREE);
}
! return name_info (var)->iv;
}
/* Determines the step of a biv defined in PHI. */
*************** find_induction_variables (void)
*** 1639,1649 ****
fprintf (tree_dump_file, "Induction variables:\n\n");
for (i = 0; i < highest_ssa_version; i++)
! if (ivs[i])
! dump_iv (tree_dump_file, ivs[i]);
}
-
return true;
}
--- 1681,1690 ----
fprintf (tree_dump_file, "Induction variables:\n\n");
for (i = 0; i < highest_ssa_version; i++)
! if (ver_info (i)->iv)
! dump_iv (tree_dump_file, ver_info (i)->iv);
}
return true;
}
*************** record_use (tree *use_p, struct iv *iv,
*** 1660,1670 ****
use->stmt = stmt;
use->op_p = use_p;
use->related_cands = BITMAP_XMALLOC ();
- use->choices = BITMAP_XMALLOC ();
- use->n_choices = 0;
- use->min_cost = INFTY;
- use->min_cost_cand = NULL;
- use->selected = NULL;
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
dump_use (tree_dump_file, use);
--- 1701,1706 ----
*************** record_use (tree *use_p, struct iv *iv,
*** 1672,1677 ****
--- 1708,1738 ----
VARRAY_PUSH_GENERIC_PTR_NOGC (iv_uses, use);
}
+ /* Checks whether OP is a loop-level invariant and if so, records it.
+ NONLINEAR_USE is true if the invariant is used in a way we do not
+ handle specially. */
+
+ static void
+ record_invariant (tree op, bool nonlinear_use)
+ {
+ basic_block bb;
+ struct version_info *info;
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return;
+
+ bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
+ if (bb
+ && flow_bb_inside_loop_p (current_loop, bb))
+ return;
+
+ info = name_info (op);
+ info->name = op;
+ info->has_nonlin_use |= nonlinear_use;
+ if (!info->inv_id)
+ info->inv_id = ++max_inv_id;
+ }
+
/* Checks whether the use *OP_P is interesting and if so, records it. */
static void
*************** find_interesting_uses_op (tree *op_p)
*** 1684,1691 ****
return;
iv = get_iv (*op_p);
! if (!iv || !iv->step || iv->have_use_for)
return;
iv->have_use_for = true;
civ = xmalloc (sizeof (struct iv));
--- 1745,1757 ----
return;
iv = get_iv (*op_p);
! if (!iv || iv->have_use_for)
return;
+ if (zero_p (iv->step))
+ {
+ record_invariant (*op_p, true);
+ return;
+ }
iv->have_use_for = true;
civ = xmalloc (sizeof (struct iv));
*************** fail:
*** 1840,1845 ****
--- 1906,1940 ----
for_each_index (op_p, idx_record_use, NULL);
}
+ /* Finds and records invariants used in STMT. */
+
+ static void
+ find_invariants_stmt (tree stmt)
+ {
+ use_optype uses = NULL;
+ unsigned i, n;
+ tree op;
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ n = PHI_NUM_ARGS (stmt);
+ else
+ {
+ get_stmt_operands (stmt);
+ uses = STMT_USE_OPS (stmt);
+ n = NUM_USES (uses);
+ }
+
+ for (i = 0; i < n; i++)
+ {
+ if (TREE_CODE (stmt) == PHI_NODE)
+ op = PHI_ARG_DEF (stmt, i);
+ else
+ op = USE_OP (uses, i);
+
+ record_invariant (op, false);
+ }
+ }
+
/* Finds interesting uses of induction variables in the statement STMT. */
static void
*************** find_interesting_uses_stmt (tree stmt)
*** 1851,1856 ****
--- 1946,1953 ----
unsigned i, n;
struct loop *loop;
+ find_invariants_stmt (stmt);
+
if (TREE_CODE (stmt) == COND_EXPR)
{
find_interesting_uses_cond (stmt, &COND_EXPR_COND (stmt));
*************** find_interesting_uses_stmt (tree stmt)
*** 1875,1881 ****
TODO -- add posibility to replace it by the known final value,
or to express the final value using the other ivs. */
! loop = outermost_usage[SSA_NAME_VERSION (lhs)];
if (loop
&& loop != current_loop
&& !flow_loop_nested_p (current_loop, loop))
--- 1972,1978 ----
TODO -- add posibility to replace it by the known final value,
or to express the final value using the other ivs. */
! loop = name_info (lhs)->outermost_usage;
if (loop
&& loop != current_loop
&& !flow_loop_nested_p (current_loop, loop))
*************** find_interesting_uses_stmt (tree stmt)
*** 1918,1924 ****
FIXME -- we do not handle this case correctly, since we just try
to replace the rhs of the phi. */
! loop = outermost_usage[SSA_NAME_VERSION (lhs)];
if (loop
&& loop != current_loop
&& !flow_loop_nested_p (current_loop, loop))
--- 2015,2021 ----
FIXME -- we do not handle this case correctly, since we just try
to replace the rhs of the phi. */
! loop = name_info (lhs)->outermost_usage;
if (loop
&& loop != current_loop
&& !flow_loop_nested_p (current_loop, loop))
*************** find_interesting_uses_stmt (tree stmt)
*** 1932,1938 ****
n = PHI_NUM_ARGS (stmt);
else
{
- get_stmt_operands (stmt);
uses = STMT_USE_OPS (stmt);
n = NUM_USES (uses);
}
--- 2029,2034 ----
*************** find_interesting_uses (void)
*** 1963,1982 ****
basic_block bb;
block_stmt_iterator bsi;
tree phi;
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
fprintf (tree_dump_file, "Uses:\n\n");
! FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
find_interesting_uses_stmt (phi);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
find_interesting_uses_stmt (bsi_stmt (bsi));
}
-
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
! fprintf (tree_dump_file, "\n");
}
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
--- 2059,2100 ----
basic_block bb;
block_stmt_iterator bsi;
tree phi;
+ basic_block *body = get_loop_body (current_loop);
+ unsigned i;
+ struct version_info *info;
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
fprintf (tree_dump_file, "Uses:\n\n");
! for (i = 0; i < current_loop->num_nodes; i++)
{
+ bb = body[i];
+
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
find_interesting_uses_stmt (phi);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
find_interesting_uses_stmt (bsi_stmt (bsi));
}
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
! {
! fprintf (tree_dump_file, "\n");
!
! for (i = 0; i < old_highest_ssa_version ; i++)
! {
! info = ver_info (i);
! if (!info->inv_id)
! continue;
!
! fprintf (tree_dump_file, " ");
! print_generic_expr (tree_dump_file, info->name, TDF_SLIM);
! fprintf (tree_dump_file, " is invariant (%d)%s\n",
! info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
! }
!
! fprintf (tree_dump_file, "\n");
! }
!
! free (body);
}
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
*************** add_candidate_1 (tree base, tree step, b
*** 2050,2056 ****
--- 2168,2176 ----
static void
add_candidate (tree base, tree step, bool important, struct iv_use *use)
{
+ #if DISABLE_IP_START
add_candidate_1 (base, step, important, IP_START, use);
+ #endif
if (ip_normal_pos ())
add_candidate_1 (base, step, important, IP_NORMAL, use);
if (ip_end_pos ())
*************** add_old_ivs_candidates (void)
*** 2096,2102 ****
for (i = 0; i < highest_ssa_version; i++)
{
! iv = ivs[i];
if (!iv || !iv->biv_p || zero_p (iv->step))
continue;
--- 2216,2222 ----
for (i = 0; i < highest_ssa_version; i++)
{
! iv = ver_info (i)->iv;
if (!iv || !iv->biv_p || zero_p (iv->step))
continue;
*************** alloc_use_cost_map (void)
*** 2230,2255 ****
}
}
! /* Sets cost of (USE, CANDIDATE) pair to COST. */
static void
! set_use_iv_cost (struct iv_use *use, struct iv_cand *cand, unsigned cost)
{
! if (cost != INFTY)
{
! bitmap_set_bit (use->choices, cand->id);
! use->n_choices++;
! if (cost < use->min_cost)
! {
! use->min_cost = cost;
! use->min_cost_cand = cand;
! }
}
if (consider_all_candidates)
{
use->cost_map[cand->id].cand = cand;
use->cost_map[cand->id].cost = cost;
return;
}
--- 2350,2374 ----
}
}
! /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
! on invariants DEPENDS_ON. */
static void
! set_use_iv_cost (struct iv_use *use, struct iv_cand *cand, unsigned cost,
! bitmap depends_on)
{
! if (cost == INFTY
! && depends_on)
{
! BITMAP_XFREE (depends_on);
! depends_on = NULL;
}
if (consider_all_candidates)
{
use->cost_map[cand->id].cand = cand;
use->cost_map[cand->id].cost = cost;
+ use->cost_map[cand->id].depends_on = depends_on;
return;
}
*************** set_use_iv_cost (struct iv_use *use, str
*** 2258,2270 ****
use->cost_map[use->n_map_members].cand = cand;
use->cost_map[use->n_map_members].cost = cost;
use->n_map_members++;
}
! /* Gets cost of (USE, CANDIDATE) pair. */
static unsigned
! get_use_iv_cost (struct iv_use *use, struct iv_cand *cand)
{
unsigned i;
--- 2377,2391 ----
use->cost_map[use->n_map_members].cand = cand;
use->cost_map[use->n_map_members].cost = cost;
+ use->cost_map[use->n_map_members].depends_on = depends_on;
use->n_map_members++;
}
! /* Gets cost of (USE, CANDIDATE) pair. Stores the bitmap of dependencies to
! DEPENDS_ON. */
static unsigned
! get_use_iv_cost (struct iv_use *use, struct iv_cand *cand, bitmap *depends_on)
{
unsigned i;
*************** get_use_iv_cost (struct iv_use *use, str
*** 2272,2286 ****
return INFTY;
if (consider_all_candidates)
! return use->cost_map[cand->id].cost;
!
! for (i = 0; i < use->n_map_members; i++)
! if (use->cost_map[i].cand == cand)
! break;
! if (i == use->n_map_members)
! return INFTY;
return use->cost_map[i].cost;
}
--- 2393,2411 ----
return INFTY;
if (consider_all_candidates)
! i = cand->id;
! else
! {
! for (i = 0; i < use->n_map_members; i++)
! if (use->cost_map[i].cand == cand)
! break;
! if (i == use->n_map_members)
! return INFTY;
! }
+ if (depends_on)
+ *depends_on = use->cost_map[i].depends_on;
return use->cost_map[i].cost;
}
*************** get_computation (struct iv_use *use, str
*** 2395,2410 ****
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase = cand->iv->base, cstep = cand->iv->step;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
! tree expr;
tree ratio;
unsigned HOST_WIDE_INT ustepi, cstepi;
HOST_WIDE_INT ratioi;
switch (cand->pos)
{
case IP_START:
expr = cand->var_after;
break;
case IP_NORMAL:
if (stmt_after_ip_normal_pos (use->stmt))
--- 2520,2537 ----
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase = cand->iv->base, cstep = cand->iv->step;
tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
! tree expr, delta;
tree ratio;
unsigned HOST_WIDE_INT ustepi, cstepi;
HOST_WIDE_INT ratioi;
switch (cand->pos)
{
+ #if DISABLE_IP_START
case IP_START:
expr = cand->var_after;
break;
+ #endif
case IP_NORMAL:
if (stmt_after_ip_normal_pos (use->stmt))
*************** get_computation (struct iv_use *use, str
*** 2455,2470 ****
&& stmt_after_ip_normal_pos (use->stmt))
cbase = fold (build (PLUS_EXPR, utype, cbase, cstep));
! /* use = ubase + ratio * (var - cbase) */
! expr = fold (build (MINUS_EXPR, utype, expr, cbase));
! if (ratioi != 1)
{
ratio = build_int_cst (utype, ratioi);
! expr = fold (build (MULT_EXPR, utype, expr, ratio));
}
-
- expr = fold (build (PLUS_EXPR, utype, ubase, expr));
return expr;
}
--- 2582,2617 ----
&& stmt_after_ip_normal_pos (use->stmt))
cbase = fold (build (PLUS_EXPR, utype, cbase, cstep));
! /* use = ubase + ratio * (var - cbase). If either cbase is a constant
! or |ratio| == 1, it is better to handle this like
!
! ubase - ratio * cbase + ratio * var. */
! if (ratioi == 1)
! {
! delta = fold (build (MINUS_EXPR, utype, ubase, cbase));
! expr = fold (build (PLUS_EXPR, utype, expr, delta));
! }
! else if (ratioi == -1)
! {
! delta = fold (build (PLUS_EXPR, utype, ubase, cbase));
! expr = fold (build (MINUS_EXPR, utype, delta, expr));
! }
! else if (TREE_CODE (cbase) == INTEGER_CST)
{
ratio = build_int_cst (utype, ratioi);
! delta = fold (build (MULT_EXPR, utype, ratio, cbase));
! delta = fold (build (MINUS_EXPR, utype, ubase, delta));
! expr = fold (build (MULT_EXPR, utype, ratio, expr));
! expr = fold (build (PLUS_EXPR, utype, delta, expr));
! }
! else
! {
! expr = fold (build (MINUS_EXPR, utype, expr, cbase));
! ratio = build_int_cst (utype, ratioi);
! expr = fold (build (MULT_EXPR, utype, ratio, expr));
! expr = fold (build (PLUS_EXPR, utype, ubase, expr));
}
return expr;
}
*************** get_address_cost (bool symbol_present, b
*** 2744,2754 ****
return cost + acost;
}
! /* Estimates cost of forcing EXPR into variable. */
static unsigned
! force_var_cost (tree expr)
{
if (is_gimple_min_invariant (expr)
|| SSA_VAR_P (expr))
return 0;
--- 2891,2928 ----
return cost + acost;
}
! /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
! the bitmap to that we should store it. */
!
! static tree
! find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
! {
! bitmap *depends_on = data;
! struct version_info *info;
!
! if (TREE_CODE (*expr_p) != SSA_NAME)
! return NULL_TREE;
! info = name_info (*expr_p);
!
! if (!info->inv_id || info->has_nonlin_use)
! return NULL_TREE;
!
! if (!*depends_on)
! *depends_on = BITMAP_XMALLOC ();
! bitmap_set_bit (*depends_on, info->inv_id);
!
! return NULL_TREE;
! }
!
! /* Estimates cost of forcing EXPR into variable. DEPENDS_ON is a set of the
! invariants the computation depends on.*/
static unsigned
! force_var_cost (tree expr, bitmap *depends_on)
{
+ if (depends_on)
+ walk_tree (&expr, find_depends, depends_on, NULL);
+
if (is_gimple_min_invariant (expr)
|| SSA_VAR_P (expr))
return 0;
*************** ptr_difference_const (tree e1, tree e2,
*** 2846,2870 ****
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
! to false if the corresponding part is missing. */
static unsigned
split_address_cost (tree addr, bool *symbol_present, bool *var_present,
! unsigned HOST_WIDE_INT *offset)
{
! while (addr
! && TREE_CODE (addr) != VAR_DECL)
! addr = peel_address (addr, offset);
! if (!addr)
{
*symbol_present = false;
*var_present = true;
return spill_cost;
}
! if (TREE_STATIC (addr)
! || DECL_EXTERNAL (addr))
{
*symbol_present = true;
*var_present = false;
--- 3020,3048 ----
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
! to false if the corresponding part is missing. DEPENDS_ON is a set of the
! invariants the computation depends on. */
static unsigned
split_address_cost (tree addr, bool *symbol_present, bool *var_present,
! unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
! tree core = addr;
! while (core
! && TREE_CODE (core) != VAR_DECL)
! core = peel_address (core, offset);
!
! if (!core)
{
*symbol_present = false;
*var_present = true;
+ walk_tree (&addr, find_depends, depends_on, NULL);
return spill_cost;
}
! if (TREE_STATIC (core)
! || DECL_EXTERNAL (core))
{
*symbol_present = true;
*var_present = false;
*************** split_address_cost (tree addr, bool *sym
*** 2879,2889 ****
/* Estimates cost of expressing difference of addresses E1 - E2 as
var + symbol + offset. The value of offset is added to OFFSET,
SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
! part is missing. */
static unsigned
ptr_difference_cost (tree e1, tree e2, bool *symbol_present, bool *var_present,
! unsigned HOST_WIDE_INT *offset)
{
unsigned HOST_WIDE_INT diff = 0;
unsigned cost;
--- 3057,3068 ----
/* Estimates cost of expressing difference of addresses E1 - E2 as
var + symbol + offset. The value of offset is added to OFFSET,
SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
! part is missing. DEPENDS_ON is a set of the invariants the computation
! depends on. */
static unsigned
ptr_difference_cost (tree e1, tree e2, bool *symbol_present, bool *var_present,
! unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
unsigned HOST_WIDE_INT diff = 0;
unsigned cost;
*************** ptr_difference_cost (tree e1, tree e2, b
*** 2903,2915 ****
if (e2 == integer_zero_node)
return split_address_cost (TREE_OPERAND (e1, 0),
! symbol_present, var_present, offset);
*symbol_present = false;
*var_present = true;
! cost = force_var_cost (e1);
! cost += force_var_cost (e2);
cost += add_cost (Pmode);
return cost;
--- 3082,3094 ----
if (e2 == integer_zero_node)
return split_address_cost (TREE_OPERAND (e1, 0),
! symbol_present, var_present, offset, depends_on);
*symbol_present = false;
*var_present = true;
! cost = force_var_cost (e1, depends_on);
! cost += force_var_cost (e2, depends_on);
cost += add_cost (Pmode);
return cost;
*************** ptr_difference_cost (tree e1, tree e2, b
*** 2918,2928 ****
/* Estimates cost of expressing difference E1 - E2 as
var + symbol + offset. The value of offset is added to OFFSET,
SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
! part is missing. */
static unsigned
difference_cost (tree e1, tree e2, bool *symbol_present, bool *var_present,
! unsigned HOST_WIDE_INT *offset)
{
unsigned cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
--- 3097,3108 ----
/* Estimates cost of expressing difference E1 - E2 as
var + symbol + offset. The value of offset is added to OFFSET,
SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
! part is missing. DEPENDS_ON is a set of the invariants the computation
! depends on. */
static unsigned
difference_cost (tree e1, tree e2, bool *symbol_present, bool *var_present,
! unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
unsigned cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
*************** difference_cost (tree e1, tree e2, bool
*** 2933,2960 ****
*offset = -*offset;
if (TREE_CODE (e1) == ADDR_EXPR)
! return ptr_difference_cost (e1, e2, symbol_present, var_present, offset);
*symbol_present = false;
! if (zero_p (e1) && zero_p (e2))
{
*var_present = false;
return 0;
}
*var_present = true;
if (zero_p (e2))
! return force_var_cost (e1);
if (zero_p (e1))
{
! cost = force_var_cost (e2);
cost += multiply_by_cost (-1, mode);
return cost;
}
! cost = force_var_cost (e1);
! cost += force_var_cost (e2);
cost += add_cost (mode);
return cost;
--- 3113,3141 ----
*offset = -*offset;
if (TREE_CODE (e1) == ADDR_EXPR)
! return ptr_difference_cost (e1, e2, symbol_present, var_present, offset,
! depends_on);
*symbol_present = false;
! if (operand_equal_p (e1, e2, 0))
{
*var_present = false;
return 0;
}
*var_present = true;
if (zero_p (e2))
! return force_var_cost (e1, depends_on);
if (zero_p (e1))
{
! cost = force_var_cost (e2, depends_on);
cost += multiply_by_cost (-1, mode);
return cost;
}
! cost = force_var_cost (e1, depends_on);
! cost += force_var_cost (e2, depends_on);
cost += add_cost (mode);
return cost;
*************** difference_cost (tree e1, tree e2, bool
*** 2963,2973 ****
/* Determines the cost of the computation by that USE is expressed
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
! register. */
static unsigned
get_computation_cost (struct iv_use *use, struct iv_cand *cand,
! bool address_p)
{
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase = cand->iv->base, cstep = cand->iv->step;
--- 3144,3155 ----
/* Determines the cost of the computation by that USE is expressed
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
! register. A set of invariants we depend on is stored in
! DEPENDS_ON. */
static unsigned
get_computation_cost (struct iv_use *use, struct iv_cand *cand,
! bool address_p, bitmap *depends_on)
{
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase = cand->iv->base, cstep = cand->iv->step;
*************** get_computation_cost (struct iv_use *use
*** 2977,2982 ****
--- 3159,3166 ----
bool var_present, symbol_present;
unsigned cost = 0, n_sums;
+ *depends_on = NULL;
+
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
/* We do not have a precision to express the values of use. */
*************** get_computation_cost (struct iv_use *use
*** 3018,3036 ****
{
offset = - ratio * int_cst_value (cbase);
cost += difference_cost (ubase, integer_zero_node,
! &symbol_present, &var_present, &offset);
}
else if (ratio == 1)
{
cost += difference_cost (ubase, cbase,
! &symbol_present, &var_present, &offset);
}
else
{
! cost += force_var_cost (cbase);
cost += add_cost (TYPE_MODE (ctype));
cost += difference_cost (ubase, integer_zero_node,
! &symbol_present, &var_present, &offset);
}
/* If we are after the "normal" position, the value of the candidate is
--- 3202,3223 ----
{
offset = - ratio * int_cst_value (cbase);
cost += difference_cost (ubase, integer_zero_node,
! &symbol_present, &var_present, &offset,
! depends_on);
}
else if (ratio == 1)
{
cost += difference_cost (ubase, cbase,
! &symbol_present, &var_present, &offset,
! depends_on);
}
else
{
! cost += force_var_cost (cbase, depends_on);
cost += add_cost (TYPE_MODE (ctype));
cost += difference_cost (ubase, integer_zero_node,
! &symbol_present, &var_present, &offset,
! depends_on);
}
/* If we are after the "normal" position, the value of the candidate is
*************** fallback:
*** 3087,3095 ****
static void
determine_use_iv_cost_generic (struct iv_use *use, struct iv_cand *cand)
{
! unsigned cost = get_computation_cost (use, cand, false);
! set_use_iv_cost (use, cand, cost);
}
/* Determines cost of basing replacement of USE on CAND in an address. */
--- 3274,3283 ----
static void
determine_use_iv_cost_generic (struct iv_use *use, struct iv_cand *cand)
{
! bitmap depends_on;
! unsigned cost = get_computation_cost (use, cand, false, &depends_on);
! set_use_iv_cost (use, cand, cost, depends_on);
}
/* Determines cost of basing replacement of USE on CAND in an address. */
*************** determine_use_iv_cost_generic (struct iv
*** 3097,3105 ****
static void
determine_use_iv_cost_address (struct iv_use *use, struct iv_cand *cand)
{
! unsigned cost = get_computation_cost (use, cand, true);
! set_use_iv_cost (use, cand, cost);
}
/* Determines cost of basing replacement of USE on CAND in a condition. */
--- 3285,3294 ----
static void
determine_use_iv_cost_address (struct iv_use *use, struct iv_cand *cand)
{
! bitmap depends_on;
! unsigned cost = get_computation_cost (use, cand, true, &depends_on);
! set_use_iv_cost (use, cand, cost, depends_on);
}
/* Determines cost of basing replacement of USE on CAND in a condition. */
*************** static void
*** 3108,3113 ****
--- 3297,3311 ----
determine_use_iv_cost_condition (struct iv_use *use, struct iv_cand *cand)
{
/* TODO implement induction variable elimination. */
+
+ if (TREE_CODE (*use->op_p) == SSA_NAME)
+ record_invariant (*use->op_p, true);
+ else
+ {
+ record_invariant (TREE_OPERAND (*use->op_p, 0), true);
+ record_invariant (TREE_OPERAND (*use->op_p, 1), true);
+ }
+
determine_use_iv_cost_generic (use, cand);
}
*************** determine_use_iv_costs (void)
*** 3194,3208 ****
use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
fprintf (tree_dump_file, "Use %d:\n", i);
! fprintf (tree_dump_file, " cand\tcost\n");
for (j = 0; j < use->n_map_members; j++)
{
! if (use->cost_map[j].cand
! && use->cost_map[j].cost != INFTY)
! fprintf (tree_dump_file, " %d\t%d\n",
! use->cost_map[j].cand->id,
! use->cost_map[j].cost);
}
fprintf (tree_dump_file, "\n");
}
fprintf (tree_dump_file, "\n");
--- 3392,3413 ----
use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
fprintf (tree_dump_file, "Use %d:\n", i);
! fprintf (tree_dump_file, " cand\tcost\tdepends on\n");
for (j = 0; j < use->n_map_members; j++)
{
! if (!use->cost_map[j].cand
! || use->cost_map[j].cost == INFTY)
! continue;
!
! fprintf (tree_dump_file, " %d\t%d\t",
! use->cost_map[j].cand->id,
! use->cost_map[j].cost);
! if (use->cost_map[j].depends_on)
! bitmap_print (tree_dump_file,
! use->cost_map[j].depends_on, "","");
! fprintf (tree_dump_file, "\n");
}
+
fprintf (tree_dump_file, "\n");
}
fprintf (tree_dump_file, "\n");
*************** determine_iv_cost (struct iv_cand *cand)
*** 3216,3235 ****
{
unsigned cost_base, cost_step;
tree base = cand->iv->base;
- tree type = TREE_TYPE (base);
/* There are two costs associated with the candidate -- its incrementation
and its initialization. The second is almost negligible for any loop
that rolls enough, so we take it just very little into account. */
if (cand->pos == IP_START)
{
/* We must decrease the base, because it will get increased just at the
start of the loop body. */
base = fold (build (MINUS_EXPR, type, base, cand->iv->step));
}
! cost_base = force_var_cost (base);
cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
/* TODO use profile to determine the ratio here. */
--- 3421,3443 ----
{
unsigned cost_base, cost_step;
tree base = cand->iv->base;
/* There are two costs associated with the candidate -- its incrementation
and its initialization. The second is almost negligible for any loop
that rolls enough, so we take it just very little into account. */
+ #if DISABLE_IP_START
+ tree type = TREE_TYPE (base);
+
if (cand->pos == IP_START)
{
/* We must decrease the base, because it will get increased just at the
start of the loop body. */
base = fold (build (MINUS_EXPR, type, base, cand->iv->step));
}
+ #endif
! cost_base = force_var_cost (base, NULL);
cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
/* TODO use profile to determine the ratio here. */
*************** init_set_costs (void)
*** 3336,3346 ****
static void
determine_set_costs (void)
{
! unsigned i, j, n;
! tree phi, stmt, op;
! use_optype uses;
! basic_block *body, bb;
! block_stmt_iterator bsi;
/* We use the following model (definitely improvable, especially the
cost function -- TODO):
--- 3544,3551 ----
static void
determine_set_costs (void)
{
! unsigned j, n;
! tree phi, op;
/* We use the following model (definitely improvable, especially the
cost function -- TODO):
*************** determine_set_costs (void)
*** 3385,3414 ****
n++;
}
! body = get_loop_body (current_loop);
! for (j = 0; j < current_loop->num_nodes; j++)
! for (bsi = bsi_start (body[j]); !bsi_end_p (bsi); bsi_next (&bsi))
! {
! stmt = bsi_stmt (bsi);
! get_stmt_operands (stmt);
! uses = STMT_USE_OPS (stmt);
!
! for (i = 0; i < NUM_USES (uses); i++)
! {
! op = USE_OP (uses, i);
!
! bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
! if (bb && flow_bb_inside_loop_p (current_loop, bb))
! continue;
! n++;
! }
! }
LOOP_DATA (current_loop)->regs_used = n;
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
fprintf (tree_dump_file, " regs_used %d\n", n);
- free (body);
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
{
--- 3590,3606 ----
n++;
}
! for (j = 0; j < old_highest_ssa_version; j++)
! {
! struct version_info *info = ver_info (j);
! if (info->inv_id && info->has_nonlin_use)
! n++;
! }
LOOP_DATA (current_loop)->regs_used = n;
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
fprintf (tree_dump_file, " regs_used %d\n", n);
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
{
*************** determine_set_costs (void)
*** 3421,3870 ****
}
}
! /* Finds a best candidate from SET to base the USE on. */
! static struct iv_cand *
! find_best_candidate (struct iv_use *use, bitmap set)
{
! unsigned j;
! unsigned bcost = INFTY, acost;
! struct iv_cand *best = NULL, *cand;
! EXECUTE_IF_SET_IN_BITMAP (set, 0, j,
{
! cand = VARRAY_GENERIC_PTR_NOGC (iv_candidates, j);
! acost = get_use_iv_cost (use, cand);
! if (acost < bcost)
{
! bcost = acost;
! best = cand;
}
- });
-
- return best;
- }
-
- /* Finds the use with the minimal number of choices. */
-
- static struct iv_use *
- use_with_min_choices (void)
- {
- struct iv_use *ret = NULL, *use;
- unsigned best = INFTY, act, i;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
! {
! use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! if (use->selected)
! continue;
! act = use->n_choices;
! if (act < best)
! {
! best = act;
! ret = use;
! if (best == 0)
! return ret;
! }
! }
! return ret;
}
! /* Calculates the minimal cost of undetermined uses. */
static unsigned
! min_remaining_cost (void)
{
unsigned i;
struct iv_use *use;
! unsigned sum = 0;
for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
{
use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! if (use->selected)
! continue;
!
! if (use->min_cost == INFTY)
! return INFTY;
!
! sum += use->min_cost;
}
! return sum;
! }
!
! /* For backtracking. */
!
! struct undo_record
! {
! struct iv_use *use; /* The use at that to perform the undo. */
!
! bitmap canceled_choices; /* The choices to readd. */
! unsigned n_canceled_choices; /* And number of them. */
!
! unsigned min_cost; /* The old min cost. */
! struct iv_cand *min_cost_cand; /* The old min cost candidate. */
!
! struct undo_record *next; /* Next undo. */
! };
!
! static struct undo_record *undo_top;
!
! /* Undoes changes up to UP_TO record. */
!
! static void
! undo_changes (struct undo_record *up_to)
! {
! struct undo_record *top, *next;
! struct iv_use *use;
!
! for (top = undo_top; top != up_to; top = next)
{
! next = top->next;
! use = top->use;
! bitmap_a_or_b (use->choices, use->choices, top->canceled_choices);
! use->n_choices += top->n_canceled_choices;
! use->min_cost = top->min_cost;
! use->min_cost_cand = top->min_cost_cand;
! BITMAP_XFREE (top->canceled_choices);
! free (top);
! }
! undo_top = up_to;
}
! /* Removes candidates in set TO_REMOVE from choices in USE, and records the
! undo. */
! static void
! execute_removal (struct iv_use *use, bitmap to_remove)
{
! unsigned size = 0, i, cost = INFTY, acost;
! struct undo_record *undo = xmalloc (sizeof (struct undo_record));
! struct iv_cand *cand = NULL, *var;
!
! undo->use = use;
! undo->canceled_choices = to_remove;
! EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, size++);
! undo->n_canceled_choices = size;
! undo->min_cost = use->min_cost;
! undo->min_cost_cand = use->min_cost_cand;
! undo->next = undo_top;
! undo_top = undo;
!
! bitmap_operation (use->choices, use->choices, to_remove, BITMAP_AND_COMPL);
! if (use->n_choices < size)
! abort ();
! use->n_choices -= size;
!
! if (!use->min_cost_cand
! || !bitmap_bit_p (to_remove, use->min_cost_cand->id))
! return;
!
! /* Recount the minimum cost candidate. */
! EXECUTE_IF_SET_IN_BITMAP (use->choices, 0, i,
! {
! var = VARRAY_GENERIC_PTR_NOGC (iv_candidates, i);
! acost = get_use_iv_cost (use, var);
! if (acost < cost)
! {
! cost = acost;
! cand = var;
! }
! });
! use->min_cost_cand = cand;
! use->min_cost = cost;
}
! /* Removes candidates from choices according to candidate chosen for USE, and
! records the changes made into undo list. If NEW_P is true, the candidate
! was added newly to the set. */
! static void
! add_forbidden_ivs (struct iv_use *use, bool new_p)
{
! unsigned i, j, cost = get_use_iv_cost (use, use->selected);
! struct iv_cand *var;
! struct iv_use *u;
! bitmap forb = BITMAP_XMALLOC (), arem;
! unsigned n_forb = 0;
! bool empty;
! /* We need to ensure that no better candidate than the one currently chosen
! for USE can be added to set. */
!
! EXECUTE_IF_SET_IN_BITMAP (use->choices, 0, i,
! {
! var = VARRAY_GENERIC_PTR_NOGC (iv_candidates, i);
!
! if (get_use_iv_cost (use, var) < cost)
! {
! bitmap_set_bit (forb, var->id);
! n_forb++;
! }
! });
!
! if (!n_forb && !new_p)
! {
! BITMAP_XFREE (forb);
! return;
! }
!
! arem = BITMAP_XMALLOC ();
!
! for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
{
! u = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! if (u->selected)
! continue;
! empty = !bitmap_a_and_b (arem, u->choices, forb);
! if (empty && !new_p)
continue;
! if (new_p)
{
! /* If use->cand is a new iv, remove all choices whose cost is greater or
! equal then the cost using this candidate. */
!
! cost = get_use_iv_cost (u, use->selected);
! if (cost != INFTY)
! {
! EXECUTE_IF_SET_IN_BITMAP (u->choices, 0, j,
! {
! var = VARRAY_GENERIC_PTR_NOGC (iv_candidates, j);
!
! if (var != use->selected
! && get_use_iv_cost (u, var) >= cost)
! {
! bitmap_set_bit (arem, var->id);
! empty = false;
! }
! });
! }
}
! if (!empty)
! {
! execute_removal (u, arem);
! arem = BITMAP_XMALLOC ();
! }
}
! BITMAP_XFREE (forb);
! BITMAP_XFREE (arem);
! }
!
! /* Tries to set candidate for use U to CAND. Meaning of the rest of arguments
! is the same as in find_optimal_iv_set_1. */
!
! static void
! try_candidate (unsigned n_selected, unsigned use_cost,
! bitmap set, unsigned n_set, unsigned iv_cost,
! bitmap best, unsigned *best_cost,
! struct iv_use *u,
! struct iv_cand *cand)
! {
! unsigned delta, var = cand->id, var_cost, size_cost, u_cost, actual_cost;
! struct undo_record *undo_till;
!
! if (bitmap_bit_p (set, var))
! {
! var_cost = 0;
! size_cost = 0;
! }
! else
{
! var_cost = cand->cost;
! size_cost = 1;
! bitmap_set_bit (set, var);
! }
!
! u_cost = get_use_iv_cost (u, cand);
! u->selected = cand;
!
! undo_till = undo_top;
! add_forbidden_ivs (u, size_cost != 0);
!
! use_cost += u_cost;
! iv_cost += var_cost;
! n_set += size_cost;
! delta = min_remaining_cost ();
!
! actual_cost = (use_cost + iv_cost
! + ivopts_global_cost_for_size (n_set) + delta);
! if (actual_cost < *best_cost)
! find_optimal_iv_set_1 (n_selected + 1, use_cost,
! set, n_set, iv_cost, best, best_cost);
!
! if (size_cost)
! bitmap_clear_bit (set, var);
! undo_changes (undo_till);
! }
! /* N_SELECTED uses have already selected their iv and and those selections
! together have cost USE_COST. Explore all possible selections of the remaining
! ones. SET is the set of chosen ivs (its size is N_SET and cost of ivs in it
! is IV_COST). The cost of the best set is in the end stored in *BEST_COST and
! the set itself in BEST. */
! static void
! find_optimal_iv_set_1 (unsigned n_selected, unsigned use_cost,
! bitmap set, unsigned n_set, unsigned iv_cost,
! bitmap best, unsigned *best_cost)
! {
! unsigned var, actual_cost;
! struct iv_cand *cand;
! struct iv_use *u;
! if (n_selected == VARRAY_ACTIVE_SIZE (iv_uses))
! {
! actual_cost = use_cost + iv_cost + ivopts_global_cost_for_size (n_set);
! if (actual_cost < *best_cost)
{
! bitmap_copy (best, set);
! *best_cost = actual_cost;
}
! return;
}
! u = use_with_min_choices ();
!
! if (!u->n_choices)
! return;
!
! EXECUTE_IF_SET_IN_BITMAP (u->choices, 0, var,
! {
! cand = VARRAY_GENERIC_PTR_NOGC (iv_candidates, var);
! try_candidate (n_selected, use_cost, set, n_set, iv_cost,
! best, best_cost, u, cand);
! });
!
! u->selected = NULL;
! }
!
! /* Computes cost of set of ivs SOL. */
!
! static unsigned
! set_cost (bitmap sol)
! {
! unsigned i;
! unsigned cost = 0, size = 0;
! struct iv_use *use;
! struct iv_cand *cand;
!
! for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
! {
! use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! cand = find_best_candidate (use, sol);
! if (!cand)
! return INFTY;
! cost += get_use_iv_cost (use, cand);
! }
!
! EXECUTE_IF_SET_IN_BITMAP (sol, 0, i,
! {
! size++;
! cand = VARRAY_GENERIC_PTR_NOGC (iv_candidates, i);
! cost += cand->cost;
! });
!
! cost += ivopts_global_cost_for_size (size);
!
! return cost;
! }
! /* Finds the initial solution greedily. */
!
! static unsigned
! get_initial_solution (bitmap sol)
! {
! unsigned i;
! struct iv_use *use;
! unsigned cost, ncost;
! bitmap psol;
!
! for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
! {
! use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! if (!use->n_choices)
! return INFTY;
!
! bitmap_set_bit (sol, use->min_cost_cand->id);
! }
!
! cost = set_cost (sol);
! psol = BITMAP_XMALLOC ();
! bitmap_copy (psol, sol);
! EXECUTE_IF_SET_IN_BITMAP (psol, 0, i,
! {
! /* Try throwing away a variable. */
! bitmap_clear_bit (sol, i);
! ncost = set_cost (sol);
! if (ncost <= cost)
! cost = ncost;
! else
! bitmap_set_bit (sol, i);
! });
! BITMAP_XFREE (psol);
! return cost;
}
/* Attempts to find the optimal set of induction variables. TODO document
! the algorithm, once it converges to the final form. For now we do something
! like optimized backtrack, but we are more then likely to finally end up
! with some heuristics. */
static bitmap
find_optimal_iv_set (void)
{
! unsigned cost = INFTY;
! bitmap set;
! bitmap best = BITMAP_XMALLOC ();
/* Set the upper bound. */
! cost = get_initial_solution (best);
if (cost == INFTY)
{
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
fprintf (tree_dump_file, "Unable to substitute for ivs, failed.\n");
! BITMAP_XFREE (best);
return NULL;
}
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
{
fprintf (tree_dump_file, "Initial set of candidates (cost %d): ", cost);
! dump_bitmap (tree_dump_file, best);
fprintf (tree_dump_file, "\n");
}
! set = BITMAP_XMALLOC ();
! find_optimal_iv_set_1 (0, 0, set, 0, 0, best, &cost);
! if (undo_top)
! abort ();
! BITMAP_XFREE (set);
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
{
! fprintf (tree_dump_file, "Best set of candidates (cost %d): ", cost);
! dump_bitmap (tree_dump_file, best);
! fprintf (tree_dump_file, "\n");
}
! return best;
}
/* Creates an induction variable with value BASE + STEP * iteration in LOOP.
--- 3613,3857 ----
}
}
! /* Finds a best candidate for USE and stores it to CAND. The candidates are
! taken from the set SOL and they may depend on invariants in the set INV.
! The really used candidate and invariants are noted to USED_IVS and
! USED_INV. */
! static unsigned
! find_best_candidate (struct iv_use *use, bitmap sol, bitmap inv,
! bitmap used_ivs, bitmap used_inv, struct iv_cand **cand)
{
! unsigned c, d;
! unsigned best_cost = INFTY, cost;
! struct iv_cand *cnd = NULL, *acnd;
! bitmap depends_on = NULL;
! EXECUTE_IF_SET_IN_BITMAP (sol, 0, c,
{
! acnd = VARRAY_GENERIC_PTR_NOGC (iv_candidates, c);
! cost = get_use_iv_cost (use, acnd, &depends_on);
!
! if (cost >= best_cost)
! goto next_cand;
! if (depends_on)
{
! EXECUTE_IF_AND_COMPL_IN_BITMAP (depends_on, inv, 0, d,
! goto next_cand);
! if (used_inv)
! bitmap_a_or_b (used_inv, used_inv, depends_on);
}
! cnd = acnd;
! best_cost = cost;
! next_cand: ;
! });
! if (cnd && used_ivs)
! bitmap_set_bit (used_ivs, cnd->id);
! if (cand)
! *cand = cnd;
! return best_cost;
}
! /* Computes cost of set of ivs SOL + invariants INV. Removes unnecessary
! induction variable candidates and invariants from the sets. */
static unsigned
! set_cost (bitmap sol, bitmap inv)
{
unsigned i;
+ unsigned cost = 0, size = 0, acost;
struct iv_use *use;
! struct iv_cand *cand;
! bitmap used_ivs = BITMAP_XMALLOC (), used_inv = BITMAP_XMALLOC ();
for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
{
use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! acost = find_best_candidate (use, sol, inv, used_ivs, used_inv, NULL);
! if (acost == INFTY)
! {
! BITMAP_XFREE (used_ivs);
! BITMAP_XFREE (used_inv);
! return INFTY;
! }
! cost += acost;
}
! EXECUTE_IF_SET_IN_BITMAP (used_ivs, 0, i,
{
! size++;
! cand = VARRAY_GENERIC_PTR_NOGC (iv_candidates, i);
! cost += cand->cost;
! });
! EXECUTE_IF_SET_IN_BITMAP (used_inv, 0, i, size++);
! cost += ivopts_global_cost_for_size (size);
! bitmap_copy (sol, used_ivs);
! bitmap_copy (inv, used_inv);
! BITMAP_XFREE (used_ivs);
! BITMAP_XFREE (used_inv);
! return cost;
}
! /* Finds an initial set of IVS and invariants INV. We do this by simply
! chosing the best candidate for each use. */
! static unsigned
! get_initial_solution (bitmap ivs, bitmap inv)
{
! unsigned i;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_candidates); i++)
! bitmap_set_bit (ivs, i);
! for (i = 1; i <= max_inv_id; i++)
! if (!ver_info (i)->has_nonlin_use)
! bitmap_set_bit (inv, i);
! return set_cost (ivs, inv);
}
! /* Tries to improve set of induction variables IVS and invariants INV to get
! it better than COST. */
! static bool
! try_improve_iv_set (bitmap ivs, bitmap inv, unsigned *cost)
{
! unsigned i, acost;
! bitmap new_ivs = BITMAP_XMALLOC (), new_inv = BITMAP_XMALLOC ();
! bitmap best_new_ivs = NULL, best_new_inv = NULL;
! /* Try altering the set of induction variables by one. */
! for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_candidates); i++)
{
! bitmap_copy (new_ivs, ivs);
! bitmap_copy (new_inv, inv);
! if (bitmap_bit_p (ivs, i))
! bitmap_clear_bit (new_ivs, i);
! else
! bitmap_set_bit (new_ivs, i);
! acost = set_cost (new_ivs, new_inv);
! if (acost >= *cost)
continue;
! if (!best_new_ivs)
{
! best_new_ivs = BITMAP_XMALLOC ();
! best_new_inv = BITMAP_XMALLOC ();
}
! *cost = acost;
! bitmap_copy (best_new_ivs, new_ivs);
! bitmap_copy (best_new_inv, new_inv);
}
! /* Ditto for invariants. */
! for (i = 1; i <= max_inv_id; i++)
{
! if (ver_info (i)->has_nonlin_use)
! continue;
! bitmap_copy (new_ivs, ivs);
! bitmap_copy (new_inv, inv);
! if (bitmap_bit_p (inv, i))
! bitmap_clear_bit (new_inv, i);
! else
! bitmap_set_bit (new_inv, i);
! acost = set_cost (new_ivs, new_inv);
! if (acost >= *cost)
! continue;
! if (!best_new_ivs)
{
! best_new_ivs = BITMAP_XMALLOC ();
! best_new_inv = BITMAP_XMALLOC ();
}
! *cost = acost;
! bitmap_copy (best_new_ivs, new_ivs);
! bitmap_copy (best_new_inv, new_inv);
}
! BITMAP_XFREE (new_ivs);
! BITMAP_XFREE (new_inv);
! if (!best_new_ivs)
! return false;
! bitmap_copy (ivs, best_new_ivs);
! bitmap_copy (inv, best_new_inv);
! BITMAP_XFREE (best_new_ivs);
! BITMAP_XFREE (best_new_inv);
! return true;
}
/* Attempts to find the optimal set of induction variables. TODO document
! the algorithm, once it converges to the final form. For now we do simple
! greedy heuristic (trying to replace at most one candidate in the selected
! solution). */
static bitmap
find_optimal_iv_set (void)
{
! unsigned cost, i;
! bitmap set = BITMAP_XMALLOC ();
! bitmap inv = BITMAP_XMALLOC ();
! struct iv_use *use;
/* Set the upper bound. */
! cost = get_initial_solution (set, inv);
if (cost == INFTY)
{
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
fprintf (tree_dump_file, "Unable to substitute for ivs, failed.\n");
! BITMAP_XFREE (inv);
! BITMAP_XFREE (set);
return NULL;
}
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
{
fprintf (tree_dump_file, "Initial set of candidates (cost %d): ", cost);
! bitmap_print (tree_dump_file, set, "", "");
! fprintf (tree_dump_file, " invariants ");
! bitmap_print (tree_dump_file, inv, "", "");
fprintf (tree_dump_file, "\n");
}
! while (try_improve_iv_set (set, inv, &cost))
! {
! if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
! {
! fprintf (tree_dump_file, "Improved to (cost %d): ", cost);
! bitmap_print (tree_dump_file, set, "", "");
! fprintf (tree_dump_file, " invariants ");
! bitmap_print (tree_dump_file, inv, "", "");
! fprintf (tree_dump_file, "\n");
! }
! }
if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
+ fprintf (tree_dump_file, "Final cost %d\n\n", cost);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
{
! use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! find_best_candidate (use, set, inv, NULL, NULL, &use->selected);
}
! BITMAP_XFREE (inv);
!
! return set;
}
/* Creates an induction variable with value BASE + STEP * iteration in LOOP.
*************** create_new_iv (struct iv_cand *cand)
*** 3933,3938 ****
--- 3920,3926 ----
switch (cand->pos)
{
+ #if DISABLE_IP_START
case IP_START:
incr_pos = bsi_start (current_loop->header);
while (!bsi_end_p (incr_pos)
*************** create_new_iv (struct iv_cand *cand)
*** 3944,3949 ****
--- 3932,3938 ----
after = true;
}
break;
+ #endif
case IP_NORMAL:
incr_pos = bsi_last (ip_normal_pos ());
*************** create_new_iv (struct iv_cand *cand)
*** 3959,3970 ****
--- 3948,3961 ----
add_referenced_tmp_var (cand->var_before);
base = unshare_expr (cand->iv->base);
+ #if DISABLE_IP_START
if (cand->pos == IP_START)
{
/* We must decrease the base, because it will get increased just at the
start of the loop body. */
base = fold (build (MINUS_EXPR, TREE_TYPE (base), base, cand->iv->step));
}
+ #endif
create_iv (base, cand->iv->step, cand->var_before, current_loop,
&incr_pos, after, &cand->var_before, &cand->var_after);
*************** rewrite_use (struct iv_use *use, struct
*** 4104,4113 ****
modify_stmt (use->stmt);
}
! /* Rewrite the uses using the induction variables in SET. */
static void
! rewrite_uses (bitmap set)
{
unsigned i;
struct iv_cand *cand;
--- 4095,4104 ----
modify_stmt (use->stmt);
}
! /* Rewrite the uses using the selected induction variables. */
static void
! rewrite_uses (void)
{
unsigned i;
struct iv_cand *cand;
*************** rewrite_uses (bitmap set)
*** 4116,4122 ****
for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
{
use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! cand = find_best_candidate (use, set);
rewrite_use (use, cand);
}
--- 4107,4115 ----
for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
{
use = VARRAY_GENERIC_PTR_NOGC (iv_uses, i);
! cand = use->selected;
! if (!cand)
! abort ();
rewrite_use (use, cand);
}
*************** rewrite_uses (bitmap set)
*** 4127,4140 ****
static void
free_loop_data (void)
{
! unsigned i;
for (i = 0; i < old_highest_ssa_version; i++)
! if (ivs[i])
! {
! free (ivs[i]);
! ivs[i] = NULL;
! }
for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
{
--- 4120,4138 ----
static void
free_loop_data (void)
{
! unsigned i, j;
for (i = 0; i < old_highest_ssa_version; i++)
! {
! struct version_info *info;
!
! info = ver_info (i);
! if (info->iv)
! free (info->iv);
! info->iv = NULL;
! info->has_nonlin_use = false;
! info->inv_id = 0;
! }
for (i = 0; i < VARRAY_ACTIVE_SIZE (iv_uses); i++)
{
*************** free_loop_data (void)
*** 4142,4148 ****
free (use->iv);
BITMAP_XFREE (use->related_cands);
! BITMAP_XFREE (use->choices);
free (use->cost_map);
free (use);
}
--- 4140,4148 ----
free (use->iv);
BITMAP_XFREE (use->related_cands);
! for (j = 0; j < use->n_map_members; j++)
! if (use->cost_map[j].depends_on)
! BITMAP_XFREE (use->cost_map[j].depends_on);
free (use->cost_map);
free (use);
}
*************** free_loop_data (void)
*** 4158,4175 ****
VARRAY_POP_ALL (iv_candidates);
if (old_highest_ssa_version != highest_ssa_version)
! {
! ivs = xrealloc (ivs, sizeof (struct iv *) * highest_ssa_version);
! memset (ivs + old_highest_ssa_version, 0,
! sizeof (struct iv *)
! * (highest_ssa_version - old_highest_ssa_version));
!
! outermost_usage = xrealloc (outermost_usage,
! sizeof (struct loop *) * highest_ssa_version);
! memset (outermost_usage + old_highest_ssa_version, 0,
! sizeof (struct loop *)
! * (highest_ssa_version - old_highest_ssa_version));
! }
for (i = 0; i < VARRAY_ACTIVE_SIZE (decl_rtl_to_reset); i++)
{
--- 4158,4170 ----
VARRAY_POP_ALL (iv_candidates);
if (old_highest_ssa_version != highest_ssa_version)
! version_info = xrealloc (version_info,
! (sizeof (struct version_info)
! * highest_ssa_version));
! memset (version_info + old_highest_ssa_version, 0,
! ((highest_ssa_version - old_highest_ssa_version)
! * sizeof (struct version_info)));
! max_inv_id = 0;
for (i = 0; i < VARRAY_ACTIVE_SIZE (decl_rtl_to_reset); i++)
{
*************** tree_ssa_iv_optimize_finalize (struct lo
*** 4198,4205 ****
}
free_loop_data ();
! free (ivs);
! free (outermost_usage);
VARRAY_FREE (decl_rtl_to_reset);
VARRAY_FREE (iv_uses);
--- 4193,4199 ----
}
free_loop_data ();
! free (version_info);
VARRAY_FREE (decl_rtl_to_reset);
VARRAY_FREE (iv_uses);
*************** tree_ssa_iv_optimize_loop (struct loop *
*** 4258,4264 ****
create_new_ivs (iv_set);
/* Rewrite the uses (item 4, part 2). */
! rewrite_uses (iv_set);
BITMAP_XFREE (iv_set);
finish:
--- 4252,4258 ----
create_new_ivs (iv_set);
/* Rewrite the uses (item 4, part 2). */
! rewrite_uses ();
BITMAP_XFREE (iv_set);
finish: