diff options
Diffstat (limited to 'gcc/lambda-code.c')
| -rw-r--r-- | gcc/lambda-code.c | 653 |
1 files changed, 560 insertions, 93 deletions
diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c index 21bea19..f438fb6 100644 --- a/gcc/lambda-code.c +++ b/gcc/lambda-code.c @@ -115,6 +115,13 @@ Fourier-Motzkin elimination is used to compute the bounds of the base space of the lattice. */ + + +DEF_VEC_GC_P(int); + +static bool perfect_nestify (struct loops *, + struct loop *, VEC (tree) *, + VEC (tree) *, VEC (int) *, VEC (tree) *); /* Lattice stuff that is internal to the code generation algorithm. */ typedef struct @@ -1160,20 +1167,23 @@ gcc_tree_to_linear_expression (int depth, tree expr, static bool invariant_in_loop (struct loop *loop, tree op) { + if (is_gimple_min_invariant (op)) + return true; if (loop->depth == 0) return true; if (TREE_CODE (op) == SSA_NAME) { + tree def; + def = SSA_NAME_DEF_STMT (op); if (TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL - && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (op))) + && IS_EMPTY_STMT (def)) return true; - if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (op))) + if (IS_EMPTY_STMT (def)) return false; - if (loop->outer) - if (!invariant_in_loop (loop->outer, op)) + if (loop->outer + && !invariant_in_loop (loop->outer, op)) return false; - return !flow_bb_inside_loop_p (loop, - bb_for_stmt (SSA_NAME_DEF_STMT (op))); + return !flow_bb_inside_loop_p (loop, bb_for_stmt (def)); } return false; } @@ -1190,7 +1200,10 @@ static lambda_loop gcc_loop_to_lambda_loop (struct loop *loop, int depth, VEC (tree) ** invariants, tree * ourinductionvar, - VEC (tree) * outerinductionvars) + VEC (tree) * outerinductionvars, + VEC (tree) ** lboundvars, + VEC (tree) ** uboundvars, + VEC (int) ** steps) { tree phi; tree exit_cond; @@ -1201,15 +1214,11 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, tree test; int stepint; int extra = 0; - tree uboundvar; + tree lboundvar, uboundvar; use_optype uses; - /* Find out induction var and set the pointer so that the caller can - append it to the outerinductionvars array later. */ - + /* Find out induction var and exit condition. */ inductionvar = find_induction_var_from_exit_cond (loop); - *ourinductionvar = inductionvar; - exit_cond = get_loop_exit_condition (loop); if (inductionvar == NULL || exit_cond == NULL) @@ -1260,7 +1269,9 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, } } - + /* The induction variable name/version we want to put in the array is the + result of the induction variable phi node. */ + *ourinductionvar = PHI_RESULT (phi); access_fn = instantiate_parameters (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi))); if (!access_fn) @@ -1316,14 +1327,20 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, } if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src)) - - lbound = gcc_tree_to_linear_expression (depth, PHI_ARG_DEF (phi, 1), - outerinductionvars, *invariants, - 0); + { + lboundvar = PHI_ARG_DEF (phi, 1); + lbound = gcc_tree_to_linear_expression (depth, lboundvar, + outerinductionvars, *invariants, + 0); + } else - lbound = gcc_tree_to_linear_expression (depth, PHI_ARG_DEF (phi, 0), - outerinductionvars, *invariants, - 0); + { + lboundvar = PHI_ARG_DEF (phi, 0); + lbound = gcc_tree_to_linear_expression (depth, lboundvar, + outerinductionvars, *invariants, + 0); + } + if (!lbound) { @@ -1368,6 +1385,11 @@ gcc_loop_to_lambda_loop (struct loop *loop, int depth, uboundvar, outerinductionvars, *invariants, extra); + VEC_safe_push (tree, *uboundvars, build (PLUS_EXPR, integer_type_node, + uboundvar, + build_int_cst (integer_type_node, extra))); + VEC_safe_push (tree, *lboundvars, lboundvar); + VEC_safe_push (int, *steps, stepint); if (!ubound) { @@ -1400,7 +1422,7 @@ find_induction_var_from_exit_cond (struct loop *loop) test = TREE_OPERAND (expr, 0); if (TREE_CODE_CLASS (TREE_CODE (test)) != '<') return NULL_TREE; - /* This is a guess. We say that for a <,!=,<= b, a is the induction + /* This is a guess. We say that for a <,!=,<= b, a is the induction variable. For >, >=, we guess b is the induction variable. If we are wrong, it'll fail the rest of the induction variable tests, and @@ -1433,15 +1455,20 @@ DEF_VEC_GC_P(lambda_loop); during this process. */ lambda_loopnest -gcc_loopnest_to_lambda_loopnest (struct loop * loop_nest, +gcc_loopnest_to_lambda_loopnest (struct loops *currloops, + struct loop * loop_nest, VEC (tree) **inductionvars, - VEC (tree) **invariants) + VEC (tree) **invariants, + bool need_perfect_nest) { lambda_loopnest ret; struct loop *temp; int depth = 0; size_t i; VEC (lambda_loop) *loops; + VEC (tree) *uboundvars; + VEC (tree) *lboundvars; + VEC (int) *steps; lambda_loop newloop; tree inductionvar = NULL; @@ -1454,18 +1481,30 @@ gcc_loopnest_to_lambda_loopnest (struct loop * loop_nest, loops = VEC_alloc (lambda_loop, 1); *inductionvars = VEC_alloc (tree, 1); *invariants = VEC_alloc (tree, 1); + lboundvars = VEC_alloc (tree, 1); + uboundvars = VEC_alloc (tree, 1); + steps = VEC_alloc (int, 1); temp = loop_nest; while (temp) { newloop = gcc_loop_to_lambda_loop (temp, depth, invariants, - &inductionvar, *inductionvars); + &inductionvar, *inductionvars, + &lboundvars, &uboundvars, + &steps); if (!newloop) return NULL; VEC_safe_push (tree, *inductionvars, inductionvar); VEC_safe_push (lambda_loop, loops, newloop); temp = temp->inner; } - + if (need_perfect_nest + && !perfect_nestify (currloops, loop_nest, + lboundvars, uboundvars, steps, *inductionvars)) + { + if (dump_file) + fprintf (dump_file, "Not a perfect nest and couldn't convert to one.\n"); + return NULL; + } ret = lambda_loopnest_new (depth, 2 * depth); for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++) LN_LOOPS (ret)[i] = newloop; @@ -1489,7 +1528,7 @@ lbv_to_gcc_expression (lambda_body_vector lbv, /* Create a statement list and a linear expression temporary. */ stmts = alloc_stmt_list (); - resvar = create_tmp_var (integer_type_node, "lletmp"); + resvar = create_tmp_var (integer_type_node, "lbvtmp"); add_referenced_tmp_var (resvar); /* Start at 0. */ @@ -1767,7 +1806,6 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, size_t depth = 0; VEC(tree) *new_ivs; block_stmt_iterator bsi; - basic_block *bbs; if (dump_file) { @@ -1849,66 +1887,56 @@ lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, i++; temp = temp->inner; } - - /* Go through the loop and make iv replacements. */ - bbs = get_loop_body (old_loopnest); - for (i = 0; i < old_loopnest->num_nodes; i++) - for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi)) - { - tree stmt = bsi_stmt (bsi); - use_optype uses; - size_t j; - - get_stmt_operands (stmt); - uses = STMT_USE_OPS (stmt); - for (j = 0; j < NUM_USES (uses); j++) - { - size_t k; - use_operand_p use = USE_OP_PTR (uses, j); - for (k = 0; k < VEC_length (tree, old_ivs); k++) - { - tree oldiv = VEC_index (tree, old_ivs, k); - if (USE_FROM_PTR (use) == oldiv) - { - tree newiv, stmts; - lambda_body_vector lbv; - - /* Compute the new expression for the induction - variable. */ - depth = VEC_length (tree, new_ivs); - lbv = lambda_body_vector_new (depth); - LBV_COEFFICIENTS (lbv)[k] = 1; - lbv = lambda_body_vector_compute_new (transform, lbv); - newiv = lbv_to_gcc_expression (lbv, new_ivs, &stmts); - - /* Insert the statements to build that - expression. */ - bsi_insert_before (&bsi, stmts, BSI_SAME_STMT); - - /* Replace the use with the result of that - expression. */ - if (dump_file) - { - fprintf (dump_file, - "Replacing induction variable use of "); - print_generic_stmt (dump_file, USE_FROM_PTR (use), 0); - fprintf (dump_file, " with "); - print_generic_stmt (dump_file, newiv, 0); - fprintf (dump_file, "\n"); - } - SET_USE (use, newiv); - } - } - - } - } + + /* Rewrite uses of the old ivs so that they are now specified in terms of + the new ivs. */ + temp = old_loopnest; + for (i = 0; i < VEC_length (tree, old_ivs); i++) + { + int j; + tree oldiv = VEC_index (tree, old_ivs, i); + dataflow_t imm = get_immediate_uses (SSA_NAME_DEF_STMT (oldiv)); + for (j = 0; j < num_immediate_uses (imm); j++) + { + size_t k; + tree stmt = immediate_use (imm, j); + use_optype uses; + get_stmt_operands (stmt); + uses = STMT_USE_OPS (stmt); + for (k = 0; k < NUM_USES (uses); k++) + { + use_operand_p use = USE_OP_PTR (uses, k); + if (USE_FROM_PTR (use) == oldiv) + { + tree newiv, stmts; + lambda_body_vector lbv; + /* Compute the new expression for the induction + variable. */ + depth = VEC_length (tree, new_ivs); + lbv = lambda_body_vector_new (depth); + LBV_COEFFICIENTS (lbv)[i] = 1; + lbv = lambda_body_vector_compute_new (transform, lbv); + newiv = lbv_to_gcc_expression (lbv, new_ivs, &stmts); + bsi = stmt_for_bsi (stmt); + /* Insert the statements to build that + expression. */ + bsi_insert_before (&bsi, stmts, BSI_SAME_STMT); + SET_USE (use, newiv); + modify_stmt (stmt); + + } + } + } + } } + /* Returns true when the vector V is lexicographically positive, in other words, when the first non zero element is positive. */ static bool -lambda_vector_lexico_pos (lambda_vector v, unsigned n) +lambda_vector_lexico_pos (lambda_vector v, + unsigned n) { unsigned i; for (i = 0; i < n; i++) @@ -1923,6 +1951,442 @@ lambda_vector_lexico_pos (lambda_vector v, unsigned n) return true; } + +/* Return TRUE if this is not interesting statement from the perspective of + determining if we have a perfect loop nest. */ + +static bool +not_interesting_stmt (tree stmt) +{ + /* Note that COND_EXPR's aren't interesting because if they were exiting the + loop, we would have already failed the number of exits tests. */ + if (TREE_CODE (stmt) == LABEL_EXPR + || TREE_CODE (stmt) == GOTO_EXPR + || TREE_CODE (stmt) == COND_EXPR) + return true; + return false; +} + +/* Return TRUE if PHI uses DEF for it's in-the-loop edge for LOOP. */ + +static bool +phi_loop_edge_uses_def (struct loop *loop, tree phi, tree def) +{ + int i; + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, i)->src)) + if (PHI_ARG_DEF (phi, i) == def) + return true; + return false; +} + +/* Return TRUE if STMT is a use of PHI_RESULT. */ + +static bool +stmt_uses_phi_result (tree stmt, tree phi_result) +{ + use_optype uses = STMT_USE_OPS (stmt); + + /* This is conservatively true, because we only want SIMPLE bumpers + of the form x +- constant for our pass. */ + if (NUM_USES (uses) != 1) + return false; + if (USE_OP (uses, 0) == phi_result) + return true; + + return false; +} + +/* STMT is a bumper stmt for LOOP if the version it defines is used in the + in-loop-edge in a phi node, and the operand it uses is the result of that + phi node. + I.E. i_29 = i_3 + 1 + i_3 = PHI (0, i_29); */ + +static bool +stmt_is_bumper_for_loop (struct loop *loop, tree stmt) +{ + tree use; + tree def; + def_optype defs = STMT_DEF_OPS (stmt); + dataflow_t imm; + int i; + + if (NUM_DEFS (defs) != 1) + return false; + def = DEF_OP (defs, 0); + imm = get_immediate_uses (stmt); + for (i = 0; i < num_immediate_uses (imm); i++) + { + use = immediate_use (imm, i); + if (TREE_CODE (use) == PHI_NODE) + { + if (phi_loop_edge_uses_def (loop, use, def)) + if (stmt_uses_phi_result (stmt, PHI_RESULT (use))) + return true; + } + } + return false; +} +/* Return true if LOOP is a perfect loop nest. + Perfect loop nests are those loop nests where all code occurs in the + innermost loop body. + If S is a program statement, then + + ie + DO I = 1, 20 + S1 + DO J = 1, 20 + ... + END DO + END DO + is not a perfect loop nest because of S1. + + DO I = 1, 20 + DO J = 1, 20 + S1 + ... + END DO + END DO + is a perfect loop nest. + + Since we don't have high level loops anymore, we basically have to walk our + statements and ignore those that are there because the loop needs them (IE + the induction variable increment, and jump back to the top of the loop). */ + +bool +perfect_nest_p (struct loop *loop) +{ + basic_block *bbs; + size_t i; + tree exit_cond; + + if (!loop->inner) + return true; + bbs = get_loop_body (loop); + exit_cond = get_loop_exit_condition (loop); + for (i = 0; i < loop->num_nodes; i++) + { + if (bbs[i]->loop_father == loop) + { + block_stmt_iterator bsi; + for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi)) + { + tree stmt = bsi_stmt (bsi); + if (stmt == exit_cond + || not_interesting_stmt (stmt) + || stmt_is_bumper_for_loop (loop, stmt)) + continue; + free (bbs); + return false; + } + } + } + free (bbs); + /* See if the inner loops are perfectly nested as well. */ + if (loop->inner) + return perfect_nest_p (loop->inner); + return true; +} + + +/* Add phi args using PENDINT_STMT list. */ + +static void +nestify_update_pending_stmts (edge e) +{ + basic_block dest; + tree phi, arg, def; + + if (!PENDING_STMT (e)) + return; + + dest = e->dest; + + for (phi = phi_nodes (dest), arg = PENDING_STMT (e); + phi; + phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg)) + { + def = TREE_VALUE (arg); + add_phi_arg (&phi, def, e); + } + + PENDING_STMT (e) = NULL; +} + +/* Replace the USES of tree X in STMT with tree Y */ + +static void +replace_uses_of_x_with_y (tree stmt, tree x, tree y) +{ + use_optype uses = STMT_USE_OPS (stmt); + size_t i; + for (i = 0; i < NUM_USES (uses); i++) + { + if (USE_OP (uses, i) == x) + SET_USE_OP (uses, i, y); + } +} + +/* Return TRUE if STMT uses tree OP in it's uses. */ + +static bool +stmt_uses_op (tree stmt, tree op) +{ + use_optype uses = STMT_USE_OPS (stmt); + size_t i; + for (i = 0; i < NUM_USES (uses); i++) + { + if (USE_OP (uses, i) == op) + return true; + } + return false; +} + +/* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect + one. LOOPIVS is a vector of induction variables, one per loop. + ATM, we only handle imperfect nests of depth 2, where all of the statements + occur after the inner loop. */ + +static bool +can_convert_to_perfect_nest (struct loop *loop, + VEC (tree) *loopivs) +{ + basic_block *bbs; + tree exit_condition; + size_t i; + block_stmt_iterator bsi; + + /* Can't handle triply nested+ loops yet. */ + if (!loop->inner || loop->inner->inner) + return false; + + /* We only handle moving the after-inner-body statements right now, so make + sure all the statements we need to move are located in that position. */ + bbs = get_loop_body (loop); + exit_condition = get_loop_exit_condition (loop); + for (i = 0; i < loop->num_nodes; i++) + { + if (bbs[i]->loop_father == loop) + { + for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi)) + { + size_t j; + tree stmt = bsi_stmt (bsi); + if (stmt == exit_condition + || not_interesting_stmt (stmt) + || stmt_is_bumper_for_loop (loop, stmt)) + continue; + /* If the statement uses inner loop ivs, we == screwed. */ + for (j = 1; j < VEC_length (tree, loopivs); j++) + if (stmt_uses_op (stmt, VEC_index (tree, loopivs, j))) + { + free (bbs); + return false; + } + + /* If the bb of a statement we care about isn't dominated by + the header of the inner loop, then we are also screwed. */ + if (!dominated_by_p (CDI_DOMINATORS, + bb_for_stmt (stmt), + loop->inner->header)) + { + free (bbs); + return false; + } + } + } + } + return true; +} + +/* 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 + STEPS is the STEPS for the loops to transform. + LOOPIVS is the induction variables for the loops to transform. + + Basically, for the case of + + FOR (i = 0; i < 50; i++) + { + FOR (j =0; j < 50; j++) + { + <whatever> + } + <some code> + } + + This function will transform it into a perfect loop nest by splitting the + outer loop into two loops, like so: + + FOR (i = 0; i < 50; i++) + { + FOR (j = 0; j < 50; j++) + { + <whatever> + } + } + + FOR (i = 0; i < 50; i ++) + { + <some code> + } + + Return FALSE if we can't make this loop into a perfect nest. */ +static bool +perfect_nestify (struct loops *loops, + struct loop *loop, + VEC (tree) *lbounds, + VEC (tree) *ubounds, + VEC (int) *steps, + VEC (tree) *loopivs) +{ + basic_block *bbs; + tree exit_condition; + tree then_label, else_label, cond_stmt; + basic_block preheaderbb, headerbb, bodybb, latchbb, olddest; + size_t i; + block_stmt_iterator bsi; + edge e; + struct loop *newloop; + tree phi; + tree uboundvar; + tree stmt; + tree ivvar, ivvarinced; + VEC (tree) *phis; + + if (!can_convert_to_perfect_nest (loop, loopivs)) + return false; + + phis = VEC_alloc (tree, 1); + + /* Create the new loop */ + + olddest = loop->single_exit->dest; + preheaderbb = loop_split_edge_with (loop->single_exit, NULL); + headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); + + /* This is done because otherwise, it will release the ssa_name too early + when the edge gets redirected and it will get reused, causing the use of + the phi node to get rewritten. */ + + 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)); + } + e = redirect_edge_and_branch (preheaderbb->succ, headerbb); + unmark_all_for_rewrite (); + bb_ann (olddest)->phi_nodes = NULL; + /* Add back the old exit phis. */ + while (VEC_length (tree, phis) != 0) + { + tree def; + tree phiname; + def = VEC_pop (tree, phis); + phiname = VEC_pop (tree, phis); + + phi = create_phi_node (phiname, preheaderbb); + add_phi_arg (&phi, def, preheaderbb->pred); + } + + nestify_update_pending_stmts (e); + bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); + latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); + make_edge (headerbb, bodybb, EDGE_FALLTHRU); + then_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (latchbb)); + else_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (olddest)); + cond_stmt = build (COND_EXPR, void_type_node, + build (NE_EXPR, boolean_type_node, + integer_one_node, + integer_zero_node), + then_label, else_label); + bsi = bsi_start (bodybb); + bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT); + e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE); + make_edge (bodybb, latchbb, EDGE_TRUE_VALUE); + make_edge (latchbb, headerbb, EDGE_FALLTHRU); + + /* Update the loop structures. */ + newloop = duplicate_loop (loops, loop, olddest->loop_father); + newloop->header = headerbb; + newloop->latch = latchbb; + newloop->single_exit = e; + add_bb_to_loop (latchbb, newloop); + add_bb_to_loop (bodybb, newloop); + add_bb_to_loop (headerbb, newloop); + add_bb_to_loop (preheaderbb, olddest->loop_father); + set_immediate_dominator (CDI_DOMINATORS, bodybb, headerbb); + set_immediate_dominator (CDI_DOMINATORS, headerbb, preheaderbb); + set_immediate_dominator (CDI_DOMINATORS, preheaderbb, + loop->single_exit->src); + set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb); + set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb); + /* Create the new iv. */ + ivvar = create_tmp_var (integer_type_node, "perfectiv"); + add_referenced_tmp_var (ivvar); + bsi = bsi_last (newloop->latch->pred->src); + create_iv (VEC_index (tree, lbounds, 0), + build_int_cst (integer_type_node, + VEC_index (int, steps, 0)), + ivvar, newloop, &bsi, false, &ivvar, &ivvarinced); + + /* Create the new upper bound. This may be not just a variable, so we copy + it to one just in case. */ + + exit_condition = get_loop_exit_condition (newloop); + uboundvar = create_tmp_var (integer_type_node, "uboundvar"); + add_referenced_tmp_var (uboundvar); + stmt = build (MODIFY_EXPR, void_type_node, uboundvar, + VEC_index (tree, ubounds, 0)); + uboundvar = make_ssa_name (uboundvar, stmt); + TREE_OPERAND (stmt, 0) = uboundvar; + bsi_insert_before (&bsi, stmt, BSI_SAME_STMT); + COND_EXPR_COND (exit_condition) = build (LE_EXPR, + boolean_type_node, + ivvarinced, + uboundvar); + + bbs = get_loop_body (loop); + /* Now replace the induction variable in the moved statements with the + correct loop induction variable. */ + for (i = 0; i < loop->num_nodes; i++) + { + block_stmt_iterator tobsi = bsi_last (bodybb); + if (bbs[i]->loop_father == loop) + { + /* Note that the bsi only needs to be explicitly incremented + when we don't move something, since it is automatically + incremented when we do. */ + for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);) + { + tree stmt = bsi_stmt (bsi); + if (stmt == exit_condition + || not_interesting_stmt (stmt) + || stmt_is_bumper_for_loop (loop, stmt)) + { + bsi_next (&bsi); + continue; + } + replace_uses_of_x_with_y (stmt, + VEC_index (tree, loopivs, 0), + ivvar); + bsi_move_before (&bsi, &tobsi); + } + } + } + free (bbs); + flow_loops_find (loops, LOOP_ALL); + return perfect_nest_p (loop); +} + /* Return true if TRANS is a legal transformation matrix that respects the dependence vectors in DISTS and DIRS. The conservative answer is false. @@ -1931,27 +2395,29 @@ lambda_vector_lexico_pos (lambda_vector v, unsigned n) matrix T is legal when applied to a loop nest with a set of lexicographically non-negative distance vectors RDG if and only if for each vector d in RDG, (T.d >= 0) is lexicographically positive. - i.e.: if and only if it transforms the lexicographically positive + ie.: if and only if it transforms the lexicographically positive distance vectors to lexicographically positive vectors. Note that a unimodular matrix must transform the zero vector (and only it) to the zero vector." S.Muchnick. */ bool -lambda_transform_legal_p (lambda_trans_matrix trans, - int nb_loops, varray_type dependence_relations) +lambda_transform_legal_p (lambda_trans_matrix trans, + int nb_loops, + varray_type dependence_relations) { unsigned int i; lambda_vector distres; struct data_dependence_relation *ddr; #if defined ENABLE_CHECKING - gcc_assert (LTM_COLSIZE (trans) == nb_loops - && LTM_ROWSIZE (trans) == nb_loops); + if (LTM_COLSIZE (trans) != nb_loops + || LTM_ROWSIZE (trans) != nb_loops) + abort (); #endif /* When there is an unknown relation in the dependence_relations, we know that it is no worth looking at this loop nest: give up. */ - ddr = (struct data_dependence_relation *) + ddr = (struct data_dependence_relation *) VARRAY_GENERIC_PTR (dependence_relations, 0); if (ddr == NULL) return true; @@ -1963,12 +2429,14 @@ lambda_transform_legal_p (lambda_trans_matrix trans, /* For each distance vector in the dependence graph. */ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) { - ddr = (struct data_dependence_relation *) + ddr = (struct data_dependence_relation *) VARRAY_GENERIC_PTR (dependence_relations, i); + + /* Don't care about relations for which we know that there is no - dependence, nor about read-read (aka. output-dependences): - these data accesses can happen in any order. */ + dependence, nor about read-read (aka. output-dependences): + these data accesses can happen in any order. */ if (DDR_ARE_DEPENDENT (ddr) == chrec_known || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr)))) continue; @@ -1977,12 +2445,11 @@ lambda_transform_legal_p (lambda_trans_matrix trans, return false; /* Compute trans.dist_vect */ - lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops, + lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops, DDR_DIST_VECT (ddr), distres); if (!lambda_vector_lexico_pos (distres, nb_loops)) return false; } - return true; } |