Public Member Functions | |
| scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_) | |
| t_bool | get_ev (tree *, tree) |
Private Member Functions | |
| t_bool | follow_ssa_edge_expr (gimple *, tree, tree *, int) |
| t_bool | follow_ssa_edge_binary (gimple *at_stmt, tree type, tree rhs0, enum tree_code code, tree rhs1, tree *evolution_of_loop, int limit) |
| t_bool | follow_ssa_edge_in_condition_phi_branch (int i, gphi *condition_phi, tree *evolution_of_branch, tree init_cond, int limit) |
| t_bool | follow_ssa_edge_in_condition_phi (gphi *condition_phi, tree *evolution_of_loop, int limit) |
| t_bool | follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node, tree *evolution_of_loop, int limit) |
| tree | add_to_evolution (tree chrec_before, enum tree_code code, tree to_add, gimple *at_stmt) |
| tree | add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt) |
Private Attributes | |
| class loop * | loop |
| gphi * | loop_phi_node |
| tree | init_cond |
Constructor & Destructor Documentation
◆ scev_dfs()
Member Function Documentation
◆ add_to_evolution()
|
private |
Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
of LOOP_NB.
Description (provided for completeness, for those who read code in
a plane, and for my poor 62 bytes brain that would have forgotten
all this in the next two or three months):
The algorithm of translation of programs from the SSA representation
into the chrecs syntax is based on a pattern matching. After having
reconstructed the overall tree expression for a loop, there are only
two cases that can arise:
1. a = loop-phi (init, a + expr)
2. a = loop-phi (init, expr)
where EXPR is either a scalar constant with respect to the analyzed
loop (this is a degree 0 polynomial), or an expression containing
other loop-phi definitions (these are higher degree polynomials).
Examples:
1.
| init = ...
| loop_1
| a = phi (init, a + 5)
| endloop
2.
| inita = ...
| initb = ...
| loop_1
| a = phi (inita, 2 * b + 3)
| b = phi (initb, b + 1)
| endloop
For the first case, the semantics of the SSA representation is:
| a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
that is, there is a loop index "x" that determines the scalar value
of the variable during the loop execution. During the first
iteration, the value is that of the initial condition INIT, while
during the subsequent iterations, it is the sum of the initial
condition with the sum of all the values of EXPR from the initial
iteration to the before last considered iteration.
For the second case, the semantics of the SSA program is:
| a (x) = init, if x = 0;
| expr (x - 1), otherwise.
The second case corresponds to the PEELED_CHREC, whose syntax is
close to the syntax of a loop-phi-node:
| phi (init, expr) vs. (init, expr)_x
The proof of the translation algorithm for the first case is a
proof by structural induction based on the degree of EXPR.
Degree 0:
When EXPR is a constant with respect to the analyzed loop, or in
other words when EXPR is a polynomial of degree 0, the evolution of
the variable A in the loop is an affine function with an initial
condition INIT, and a step EXPR. In order to show this, we start
from the semantics of the SSA representation:
f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
and since "expr (j)" is a constant with respect to "j",
f (x) = init + x * expr
Finally, based on the semantics of the pure sum chrecs, by
identification we get the corresponding chrecs syntax:
f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
f (x) -> {init, +, expr}_x
Higher degree:
Suppose that EXPR is a polynomial of degree N with respect to the
analyzed loop_x for which we have already determined that it is
written under the chrecs syntax:
| expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
We start from the semantics of the SSA program:
| f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
|
| f (x) = init + \sum_{j = 0}^{x - 1}
| (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
|
| f (x) = init + \sum_{j = 0}^{x - 1}
| \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
|
| f (x) = init + \sum_{k = 0}^{n - 1}
| (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
|
| f (x) = init + \sum_{k = 0}^{n - 1}
| (b_k * \binom{x}{k + 1})
|
| f (x) = init + b_0 * \binom{x}{1} + ...
| + b_{n-1} * \binom{x}{n}
|
| f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
| + b_{n-1} * \binom{x}{n}
|
And finally from the definition of the chrecs syntax, we identify:
| f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
This shows the mechanism that stands behind the add_to_evolution
function. An important point is that the use of symbolic
parameters avoids the need of an analysis schedule.
Example:
| inita = ...
| initb = ...
| loop_1
| a = phi (inita, a + 2 + b)
| b = phi (initb, b + 1)
| endloop
When analyzing "a", the algorithm keeps "b" symbolically:
| a -> {inita, +, 2 + b}_1
Then, after instantiation, the analyzer ends on the evolution:
| a -> {inita, +, 2 + initb, +, 1}_1
References add_to_evolution_1(), build_int_cst_type(), build_real(), chrec_dont_know, chrec_fold_multiply(), chrec_type(), dconstm1, dump_file, dump_flags, NULL_TREE, loop::num, print_generic_expr(), SCALAR_FLOAT_TYPE_P, TDF_SCEV, and TREE_CODE.
Referenced by follow_ssa_edge_binary(), and follow_ssa_edge_expr().
◆ add_to_evolution_1()
Helper function for add_to_evolution. Returns the evolution function for an assignment of the form "a = b + c", where "a" and "b" are on the strongly connected component. CHREC_BEFORE is the information that we already have collected up to this point. TO_ADD is the evolution of "c". When CHREC_BEFORE has an evolution part in LOOP_NB, add to this evolution the expression TO_ADD, otherwise construct an evolution part for this loop.
References add_to_evolution_1(), build_int_cst(), build_polynomial_chrec(), build_real(), chrec_convert(), chrec_convert_rhs(), chrec_dont_know, chrec_fold_plus(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, dconst0, flow_loop_nested_p(), fold_convert, gcc_assert, get_chrec_loop(), gimple_phi_result(), init_cond, loop_phi_node, loop::num, SCALAR_FLOAT_TYPE_P, STRIP_NOPS, TREE_CODE, TREE_TYPE, and type().
Referenced by add_to_evolution(), and add_to_evolution_1().
◆ follow_ssa_edge_binary()
|
private |
Follow the ssa edge into the binary expression RHS0 CODE RHS1. Return true if the strongly connected component has been found.
References add_to_evolution(), chrec_convert(), follow_ssa_edge_expr(), gcc_unreachable, t_false, t_true, and TREE_CODE.
Referenced by follow_ssa_edge_expr().
◆ follow_ssa_edge_expr()
|
private |
Follow the ssa edge into the expression EXPR. Return true if the strongly connected component has been found.
References add_to_evolution(), CASE_CONVERT, chrec_convert(), chrec_dont_know, dyn_cast(), expr, flow_loop_nested_p(), follow_ssa_edge_binary(), follow_ssa_edge_expr(), follow_ssa_edge_in_condition_phi(), follow_ssa_edge_inner_loop_phi(), get_gimple_rhs_class(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), GIMPLE_BINARY_RHS, gimple_nop_p(), GIMPLE_SINGLE_RHS, GIMPLE_UNARY_RHS, is_gimple_assign(), loop_containing_stmt(), loop_phi_node, loop_phi_node_p(), NULL_TREE, SSA_NAME_DEF_STMT, STRIP_USELESS_TYPE_CONVERSION, t_dont_know, t_false, t_true, TREE_CODE, tree_nop_conversion_p(), TREE_OPERAND, TREE_TYPE, and type().
Referenced by follow_ssa_edge_binary(), follow_ssa_edge_expr(), follow_ssa_edge_in_condition_phi_branch(), follow_ssa_edge_inner_loop_phi(), and get_ev().
◆ follow_ssa_edge_in_condition_phi()
|
private |
This function merges the branches of a condition-phi-node in a loop.
References chrec_dont_know, chrec_merge(), follow_ssa_edge_in_condition_phi_branch(), gimple_phi_num_args(), i, t_dont_know, t_false, and t_true.
Referenced by follow_ssa_edge_expr().
◆ follow_ssa_edge_in_condition_phi_branch()
|
private |
Helper function for one branch of the condition-phi-node. Return true if the strongly connected component has been found following this path.
References backedge_phi_arg_p(), chrec_dont_know, follow_ssa_edge_expr(), i, init_cond, PHI_ARG_DEF, t_false, and TREE_CODE.
Referenced by follow_ssa_edge_in_condition_phi().
◆ follow_ssa_edge_inner_loop_phi()
|
private |
Follow an SSA edge in an inner loop. It computes the overall effect of the loop, and following the symbolic initial conditions, it follows the edges in the parent loop. The inner loop is considered as a single statement.
References analyze_scalar_evolution(), chrec_dont_know, compute_overall_effect_of_inner_loop(), flow_bb_inside_loop_p(), follow_ssa_edge_expr(), gimple_phi_arg_edge(), gimple_phi_num_args(), i, loop_containing_stmt(), loop_phi_node, PHI_ARG_DEF, PHI_RESULT, t_false, and t_true.
Referenced by follow_ssa_edge_expr().
◆ get_ev()
References chrec_dont_know, follow_ssa_edge_expr(), and loop_phi_node.
Referenced by analyze_evolution_in_loop().
Field Documentation
◆ init_cond
|
private |
Referenced by add_to_evolution_1(), and follow_ssa_edge_in_condition_phi_branch().
◆ loop
|
private |
◆ loop_phi_node
|
private |
Referenced by add_to_evolution_1(), follow_ssa_edge_expr(), follow_ssa_edge_inner_loop_phi(), and get_ev().
The documentation for this class was generated from the following file:
