Fourier-Motzkin elimination is used to compute the bounds of the base space
of the lattice. */
-static bool perfect_nestify (struct loops *,
- struct loop *, VEC(tree,heap) *,
+static bool perfect_nestify (struct loop *, VEC(tree,heap) *,
VEC(tree,heap) *, VEC(int,heap) *,
VEC(tree,heap) *);
/* Lattice stuff that is internal to the code generation algorithm. */
/* Compute the least common multiple of two numbers A and B . */
-static int
-lcm (int a, int b)
+int
+least_common_multiple (int a, int b)
{
return (abs (a) * abs (b) / gcd (a, b));
}
{
if (A[k][i] < 0)
{
- multiple = lcm (A[j][i], A[k][i]);
+ multiple = least_common_multiple (A[j][i], A[k][i]);
f1 = multiple / A[j][i];
f2 = -1 * multiple / A[k][i];
during this process. */
lambda_loopnest
-gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
- struct loop *loop_nest,
+gcc_loopnest_to_lambda_loopnest (struct loop *loop_nest,
VEC(tree,heap) **inductionvars,
VEC(tree,heap) **invariants)
{
if (!perfect_nest)
{
- if (!perfect_nestify (currloops, loop_nest,
- lboundvars, uboundvars, steps, *inductionvars))
+ if (!perfect_nestify (loop_nest, lboundvars, uboundvars, steps,
+ *inductionvars))
{
if (dump_file)
fprintf (dump_file,
type,
new_ivs,
invariants, MIN_EXPR, &stmts);
- exit = temp->single_exit;
+ exit = single_exit (temp);
exitcond = get_loop_exit_condition (temp);
bb = bb_for_stmt (exitcond);
bsi = bsi_start (bb);
return true;
}
-/* Replace the USES of X in STMT, or uses with the same step as X with Y. */
+/* Replace the USES of X in STMT, or uses with the same step as X with Y.
+ YINIT is the initial value of Y, REPLACEMENTS is a hash table to
+ avoid creating duplicate temporaries and FIRSTBSI is statement
+ iterator where new temporaries should be inserted at the beginning
+ of body basic block. */
static void
replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
- int xstep, tree y)
+ int xstep, tree y, tree yinit,
+ htab_t replacements,
+ block_stmt_iterator *firstbsi)
{
ssa_op_iter iter;
use_operand_p use_p;
{
tree use = USE_FROM_PTR (use_p);
tree step = NULL_TREE;
- tree scev = instantiate_parameters (loop,
- analyze_scalar_evolution (loop, use));
+ tree scev, init, val, var, setstmt;
+ struct tree_map *h, in;
+ void **loc;
- if (scev != NULL_TREE && scev != chrec_dont_know)
- step = evolution_part_in_loop_num (scev, loop->num);
+ /* Replace uses of X with Y right away. */
+ if (use == x)
+ {
+ SET_USE (use_p, y);
+ continue;
+ }
+
+ scev = instantiate_parameters (loop,
+ analyze_scalar_evolution (loop, use));
+
+ if (scev == NULL || scev == chrec_dont_know)
+ continue;
+
+ step = evolution_part_in_loop_num (scev, loop->num);
+ if (step == NULL
+ || step == chrec_dont_know
+ || TREE_CODE (step) != INTEGER_CST
+ || int_cst_value (step) != xstep)
+ continue;
+
+ /* Use REPLACEMENTS hash table to cache already created
+ temporaries. */
+ in.hash = htab_hash_pointer (use);
+ in.from = use;
+ h = htab_find_with_hash (replacements, &in, in.hash);
+ if (h != NULL)
+ {
+ SET_USE (use_p, h->to);
+ continue;
+ }
+
+ /* USE which has the same step as X should be replaced
+ with a temporary set to Y + YINIT - INIT. */
+ init = initial_condition_in_loop_num (scev, loop->num);
+ gcc_assert (init != NULL && init != chrec_dont_know);
+ if (TREE_TYPE (use) == TREE_TYPE (y))
+ {
+ val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), init, yinit);
+ val = fold_build2 (PLUS_EXPR, TREE_TYPE (y), y, val);
+ if (val == y)
+ {
+ /* If X has the same type as USE, the same step
+ and same initial value, it can be replaced by Y. */
+ SET_USE (use_p, y);
+ continue;
+ }
+ }
+ else
+ {
+ val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), y, yinit);
+ val = fold_convert (TREE_TYPE (use), val);
+ val = fold_build2 (PLUS_EXPR, TREE_TYPE (use), val, init);
+ }
- if ((step && step != chrec_dont_know
- && TREE_CODE (step) == INTEGER_CST
- && int_cst_value (step) == xstep)
- || USE_FROM_PTR (use_p) == x)
- SET_USE (use_p, y);
+ /* Create a temporary variable and insert it at the beginning
+ of the loop body basic block, right after the PHI node
+ which sets Y. */
+ var = create_tmp_var (TREE_TYPE (use), "perfecttmp");
+ add_referenced_var (var);
+ val = force_gimple_operand_bsi (firstbsi, val, false, NULL);
+ setstmt = build2 (MODIFY_EXPR, void_type_node, var, val);
+ var = make_ssa_name (var, setstmt);
+ TREE_OPERAND (setstmt, 0) = var;
+ bsi_insert_before (firstbsi, setstmt, BSI_SAME_STMT);
+ update_stmt (setstmt);
+ SET_USE (use_p, var);
+ h = ggc_alloc (sizeof (struct tree_map));
+ h->hash = in.hash;
+ h->from = use;
+ h->to = var;
+ loc = htab_find_slot_with_hash (replacements, h, in.hash, INSERT);
+ gcc_assert ((*(struct tree_map **)loc) == NULL);
+ *(struct tree_map **) loc = h;
}
}
if (TREE_CODE (stmt) != PHI_NODE
|| PHI_NUM_ARGS (stmt) != 1
- || bb_for_stmt (stmt) != loop->single_exit->dest)
+ || bb_for_stmt (stmt) != single_exit (loop)->dest)
return false;
return true;
/* We also need to make sure the loop exit only has simple copy phis in it,
otherwise we don't know how to transform it into a perfect nest right
now. */
- exitdest = loop->single_exit->dest;
+ exitdest = single_exit (loop)->dest;
for (phi = phi_nodes (exitdest); phi; phi = PHI_CHAIN (phi))
if (PHI_NUM_ARGS (phi) != 1)
}
/* Transform the loop nest into a perfect nest, if possible.
- LOOPS is the current struct loops *
LOOP is the loop nest to transform into a perfect nest
LBOUNDS are the lower bounds for the loops to transform
UBOUNDS are the upper bounds for the loops to transform
Return FALSE if we can't make this loop into a perfect nest. */
static bool
-perfect_nestify (struct loops *loops,
- struct loop *loop,
+perfect_nestify (struct loop *loop,
VEC(tree,heap) *lbounds,
VEC(tree,heap) *ubounds,
VEC(int,heap) *steps,
tree then_label, else_label, cond_stmt;
basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
int i;
- block_stmt_iterator bsi;
+ block_stmt_iterator bsi, firstbsi;
bool insert_after;
edge e;
struct loop *newloop;
tree stmt;
tree oldivvar, ivvar, ivvarinced;
VEC(tree,heap) *phis = NULL;
-
+ htab_t replacements = NULL;
+
/* Create the new loop. */
- olddest = loop->single_exit->dest;
- preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
+ olddest = single_exit (loop)->dest;
+ preheaderbb = split_edge (single_exit (loop));
headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
/* Push the exit phi nodes that we are moving. */
make_edge (latchbb, headerbb, EDGE_FALLTHRU);
/* Update the loop structures. */
- newloop = duplicate_loop (loops, loop, olddest->loop_father);
+ newloop = duplicate_loop (loop, olddest->loop_father);
newloop->header = headerbb;
newloop->latch = latchbb;
- newloop->single_exit = e;
+ set_single_exit (newloop, e);
add_bb_to_loop (latchbb, newloop);
add_bb_to_loop (bodybb, newloop);
add_bb_to_loop (headerbb, newloop);
set_immediate_dominator (CDI_DOMINATORS, bodybb, headerbb);
set_immediate_dominator (CDI_DOMINATORS, headerbb, preheaderbb);
set_immediate_dominator (CDI_DOMINATORS, preheaderbb,
- loop->single_exit->src);
+ single_exit (loop)->src);
set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb);
/* Create the new iv. */
uboundvar,
ivvarinced);
update_stmt (exit_condition);
+ replacements = htab_create_ggc (20, tree_map_hash,
+ tree_map_eq, NULL);
bbs = get_loop_body_in_dom_order (loop);
/* Now move the statements, and replace the induction variable in the moved
statements with the correct loop induction variable. */
oldivvar = VEC_index (tree, loopivs, 0);
+ firstbsi = bsi_start (bodybb);
for (i = loop->num_nodes - 1; i >= 0 ; i--)
{
block_stmt_iterator tobsi = bsi_last (bodybb);
if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
{
- for (bsi = bsi_last (bbs[i]); !bsi_end_p (bsi);)
+ block_stmt_iterator header_bsi
+ = bsi_after_labels (loop->inner->header);
+
+ for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
{
- use_operand_p use_p;
- imm_use_iterator imm_iter;
- tree imm_stmt;
tree stmt = bsi_stmt (bsi);
if (stmt == exit_condition
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
{
- if (!bsi_end_p (bsi))
- bsi_prev (&bsi);
+ bsi_next (&bsi);
continue;
}
-
- /* Make copies of this statement to put it back next
- to its uses. */
- FOR_EACH_IMM_USE_STMT (imm_stmt, imm_iter,
- TREE_OPERAND (stmt, 0))
- {
- if (!exit_phi_for_loop_p (loop->inner, imm_stmt))
- {
- block_stmt_iterator tobsi;
- tree newname;
- tree newstmt;
-
- newstmt = unshare_expr (stmt);
- tobsi = bsi_after_labels (bb_for_stmt (imm_stmt));
- newname = TREE_OPERAND (newstmt, 0);
- newname = SSA_NAME_VAR (newname);
- newname = make_ssa_name (newname, newstmt);
- TREE_OPERAND (newstmt, 0) = newname;
-
- FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
- SET_USE (use_p, newname);
-
- bsi_insert_before (&tobsi, newstmt, BSI_SAME_STMT);
- update_stmt (newstmt);
- update_stmt (imm_stmt);
- }
- }
- if (!bsi_end_p (bsi))
- bsi_prev (&bsi);
+
+ bsi_move_before (&bsi, &header_bsi);
}
}
else
}
replace_uses_equiv_to_x_with_y
- (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar);
+ (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar,
+ VEC_index (tree, lbounds, 0), replacements, &firstbsi);
bsi_move_before (&bsi, &tobsi);
}
free (bbs);
+ htab_delete (replacements);
return perfect_nest_p (loop);
}
OSDN Git Service
