A loop iteration space represents the points traversed by the loop. A point in the
iteration space can be represented by a vector of size <loop depth>. You can
- therefore represent the iteration space as a integral combinations of a set
+ therefore represent the iteration space as an integral combinations of a set
of basis vectors.
A loop iteration space is dense if every integer point between the loop
}
/* Compute the loop bounds for the auxiliary space NEST.
- Input system used is Ax <= b. TRANS is the unimodular transformation. */
+ Input system used is Ax <= b. TRANS is the unimodular transformation.
+ Given the original nest, this function will
+ 1. Convert the nest into matrix form, which consists of a matrix for the
+ coefficients, a matrix for the
+ invariant coefficients, and a vector for the constants.
+ 2. Use the matrix form to calculate the lattice base for the nest (which is
+ a dense space)
+ 3. Compose the dense space transform with the user specified transform, to
+ get a transform we can easily calculate transformed bounds for.
+ 4. Multiply the composed transformation matrix times the matrix form of the
+ loop.
+ 5. Transform the newly created matrix (from step 4) back into a loop nest
+ using fourier motzkin elimination to figure out the bounds. */
static lambda_loopnest
lambda_compute_auxillary_space (lambda_loopnest nest,
}
/* Compute the loop bounds for the target space, using the bounds of
- the auxiliary nest AUXILLARY_NEST, and the triangular matrix H. This is
- done by matrix multiplication and then transformation of the new matrix
- back into linear expression form.
+ the auxiliary nest AUXILLARY_NEST, and the triangular matrix H.
+ The target space loop bounds are computed by multiplying the triangular
+ matrix H by the auxillary nest, to get the new loop bounds. The sign of
+ the loop steps (positive or negative) is then used to swap the bounds if
+ the loop counts downwards.
Return the target loopnest. */
static lambda_loopnest
{
lambda_loop newloop;
basic_block bb;
+ edge exit;
tree ivvar, ivvarinced, exitcond, stmts;
enum tree_code testtype;
tree newupperbound, newlowerbound;
new_ivs,
invariants, MAX_EXPR, &stmts);
bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
- bsi_commit_edge_inserts (NULL);
+ bsi_commit_edge_inserts ();
/* Build the new upper bound and insert its statements in the
basic block of the exit condition */
newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
type,
new_ivs,
invariants, MIN_EXPR, &stmts);
+ exit = temp->single_exit;
exitcond = get_loop_exit_condition (temp);
bb = bb_for_stmt (exitcond);
bsi = bsi_start (bb);
testtype = LL_STEP (newloop) >= 0 ? LE_EXPR : GE_EXPR;
- /* Since we don't know which cond_expr part currently points to each
- edge, check which one is invariant and make sure we reverse the
- comparison if we are trying to replace a <= 50 with 50 >= newiv.
- This ensures that we still canonicalize to <invariant> <test>
- <induction variable>. */
- if (!expr_invariant_in_loop_p (temp, TREE_OPERAND (exitcond, 0)))
+ /* We want to build a conditional where true means exit the loop, and
+ false means continue the loop.
+ So swap the testtype if this isn't the way things are.*/
+
+ if (exit->flags & EDGE_FALSE_VALUE)
testtype = swap_tree_comparison (testtype);
-
+
COND_EXPR_COND (exitcond) = build (testtype,
boolean_type_node,
newupperbound, ivvarinced);
VEC (tree) *loopivs)
{
basic_block *bbs;
- tree exit_condition;
+ tree exit_condition, phi;
size_t i;
block_stmt_iterator bsi;
+ basic_block exitdest;
/* Can't handle triply nested+ loops yet. */
if (!loop->inner || loop->inner->inner)
}
}
}
+
+ /* 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;
+
+ for (phi = phi_nodes (exitdest); phi; phi = PHI_CHAIN (phi))
+ if (PHI_NUM_ARGS (phi) != 1)
+ return false;
+
return true;
}
for (phi = phi_nodes (olddest); phi; phi = PHI_CHAIN (phi))
{
- /* These should be simple exit phi copies. */
- if (PHI_NUM_ARGS (phi) != 1)
- return false;
VEC_safe_push (tree, phis, PHI_RESULT (phi));
VEC_safe_push (tree, phis, PHI_ARG_DEF (phi, 0));
mark_for_rewrite (PHI_RESULT (phi));
def = VEC_pop (tree, phis);
phiname = VEC_pop (tree, phis);
phi = create_phi_node (phiname, preheaderbb);
- add_phi_arg (&phi, def, EDGE_PRED (preheaderbb, 0));
+ add_phi_arg (phi, def, EDGE_PRED (preheaderbb, 0));
}
flush_pending_stmts (e);
unmark_all_for_rewrite ();
OSDN Git Service
