You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/*
Description:
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
#include "tree.h"
return &res->chrec;
}
-/* Tries to express CHREC in wider type TYPE. */
-
-tree
-count_ev_in_wider_type (tree type, tree chrec)
-{
- tree base, step;
- struct loop *loop;
-
- if (!evolution_function_is_affine_p (chrec))
- return fold_convert (type, chrec);
-
- base = CHREC_LEFT (chrec);
- step = CHREC_RIGHT (chrec);
- loop = current_loops->parray[CHREC_VARIABLE (chrec)];
-
- /* TODO -- if we knew the statement at that the conversion occurs,
- we could pass it to can_count_iv_in_wider_type and get a better
- result. */
- step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE);
- if (!step)
- return fold_convert (type, chrec);
- base = chrec_convert (type, base);
-
- return build_polynomial_chrec (CHREC_VARIABLE (chrec),
- base, step);
-}
-
/* Return true when CHREC contains symbolic names defined in
LOOP_NB. */
count of the loop in order to be compatible with the other
nb_iter computations in loop-iv. This also allows the
representation of nb_iters that are equal to MAX_INT. */
- if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0)
- || TREE_OVERFLOW (res))
+ if (TREE_CODE (res) == INTEGER_CST
+ && (TREE_INT_CST_LOW (res) == 0
+ || TREE_OVERFLOW (res)))
res = chrec_dont_know;
if (dump_file && (dump_flags & TDF_DETAILS))
static void
get_exit_conditions_rec (struct loop *loop,
- varray_type *exit_conditions)
+ VEC(tree,heap) **exit_conditions)
{
if (!loop)
return;
tree loop_condition = get_loop_exit_condition (loop);
if (loop_condition)
- VARRAY_PUSH_TREE (*exit_conditions, loop_condition);
+ VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
}
}
static void
select_loops_exit_conditions (struct loops *loops,
- varray_type *exit_conditions)
+ VEC(tree,heap) **exit_conditions)
{
struct loop *function_body = loops->parray[0];
static bool
follow_ssa_edge_in_rhs (struct loop *loop,
+ tree at_stmt,
tree rhs,
tree halting_phi,
tree *evolution_of_loop)
{
case NOP_EXPR:
/* This assignment is under the form "a_1 = (cast) rhs. */
- res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi,
- evolution_of_loop);
- *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
+ res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
+ halting_phi, evolution_of_loop);
+ *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
+ *evolution_of_loop, at_stmt);
break;
case INTEGER_CST:
if (res)
*evolution_of_loop = add_to_evolution
(loop->num,
- chrec_convert (type_rhs, *evolution_of_loop),
+ chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
PLUS_EXPR, rhs1);
else
if (res)
*evolution_of_loop = add_to_evolution
(loop->num,
- chrec_convert (type_rhs, *evolution_of_loop),
+ chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
PLUS_EXPR, rhs0);
}
}
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
+ (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+ at_stmt),
PLUS_EXPR, rhs1);
}
}
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
+ (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+ at_stmt),
PLUS_EXPR, rhs0);
}
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
+ (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+ at_stmt),
MINUS_EXPR, rhs1);
}
else
/* Follow the edges that exit the inner loop. */
bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
if (!flow_bb_inside_loop_p (loop, bb))
- res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
+ res = res || follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
+ arg, halting_phi,
evolution_of_loop);
}
/* Otherwise, compute the overall effect of the inner loop. */
ev = compute_overall_effect_of_inner_loop (loop, ev);
- return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
+ return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
evolution_of_loop);
}
return false;
case MODIFY_EXPR:
- return follow_ssa_edge_in_rhs (loop,
+ return follow_ssa_edge_in_rhs (loop, def,
TREE_OPERAND (def, 1),
halting_phi,
evolution_of_loop);
}
/* Interpret the right hand side of a modify_expr OPND1. If we didn't
- analyzed this node before, follow the definitions until ending
+ analyze this node before, follow the definitions until ending
either on an analyzed modify_expr, or on a loop-phi-node. On the
return path, this function propagates evolutions (ala constant copy
propagation). OPND1 is not a GIMPLE expression because we could
analyze the effect of an inner loop: see interpret_loop_phi. */
static tree
-interpret_rhs_modify_expr (struct loop *loop,
+interpret_rhs_modify_expr (struct loop *loop, tree at_stmt,
tree opnd1, tree type)
{
tree res, opnd10, opnd11, chrec10, chrec11;
-
+
if (is_gimple_min_invariant (opnd1))
- return chrec_convert (type, opnd1);
-
+ return chrec_convert (type, opnd1, at_stmt);
+
switch (TREE_CODE (opnd1))
{
case PLUS_EXPR:
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10);
- chrec11 = chrec_convert (type, chrec11);
+ chrec10 = chrec_convert (type, chrec10, at_stmt);
+ chrec11 = chrec_convert (type, chrec11, at_stmt);
res = chrec_fold_plus (type, chrec10, chrec11);
break;
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10);
- chrec11 = chrec_convert (type, chrec11);
+ chrec10 = chrec_convert (type, chrec10, at_stmt);
+ chrec11 = chrec_convert (type, chrec11, at_stmt);
res = chrec_fold_minus (type, chrec10, chrec11);
break;
case NEGATE_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
chrec10 = analyze_scalar_evolution (loop, opnd10);
- chrec10 = chrec_convert (type, chrec10);
+ chrec10 = chrec_convert (type, chrec10, at_stmt);
res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10);
break;
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10);
- chrec11 = chrec_convert (type, chrec11);
+ chrec10 = chrec_convert (type, chrec10, at_stmt);
+ chrec11 = chrec_convert (type, chrec11, at_stmt);
res = chrec_fold_multiply (type, chrec10, chrec11);
break;
case SSA_NAME:
- res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
+ res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
+ at_stmt);
break;
case ASSERT_EXPR:
opnd10 = ASSERT_EXPR_VAR (opnd1);
- res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10));
+ res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
+ at_stmt);
break;
case NOP_EXPR:
case CONVERT_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
chrec10 = analyze_scalar_evolution (loop, opnd10);
- res = chrec_convert (type, chrec10);
+ res = chrec_convert (type, chrec10, at_stmt);
break;
default:
return chrec_dont_know;
if (TREE_CODE (var) != SSA_NAME)
- return interpret_rhs_modify_expr (loop, var, type);
+ return interpret_rhs_modify_expr (loop, NULL_TREE, var, type);
def = SSA_NAME_DEF_STMT (var);
bb = bb_for_stmt (def);
switch (TREE_CODE (def))
{
case MODIFY_EXPR:
- res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type);
+ res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type);
break;
case PHI_NODE:
if (op0 == TREE_OPERAND (chrec, 0))
return chrec;
- return chrec_convert (TREE_TYPE (chrec), op0);
+ return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
case SCEV_NOT_KNOWN:
return chrec_dont_know;
&& op2 == TREE_OPERAND (chrec, 2))
return chrec;
- return fold (build (TREE_CODE (chrec),
- TREE_TYPE (chrec), op0, op1, op2));
+ return fold_build3 (TREE_CODE (chrec),
+ TREE_TYPE (chrec), op0, op1, op2);
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
if (op0 == TREE_OPERAND (chrec, 0)
&& op1 == TREE_OPERAND (chrec, 1))
return chrec;
- return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
+ return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
case 1:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0))
return chrec;
- return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
+ return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
case 0:
return chrec;
from the EXIT_CONDITIONS array. */
static void
-number_of_iterations_for_all_loops (varray_type exit_conditions)
+number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
{
unsigned int i;
unsigned nb_chrec_dont_know_loops = 0;
unsigned nb_static_loops = 0;
+ tree cond;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
+ for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
{
- tree res = number_of_iterations_in_loop
- (loop_containing_stmt (VARRAY_TREE (exit_conditions, i)));
+ tree res = number_of_iterations_in_loop (loop_containing_stmt (cond));
if (chrec_contains_undetermined (res))
nb_chrec_dont_know_loops++;
else
index. This allows the parallelization of the loop. */
static void
-analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions)
+analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
{
unsigned int i;
struct chrec_stats stats;
+ tree cond;
reset_chrecs_counters (&stats);
- for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
+ for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
{
struct loop *loop;
basic_block bb;
tree phi, chrec;
- loop = loop_containing_stmt (VARRAY_TREE (exit_conditions, i));
+ loop = loop_containing_stmt (cond);
bb = loop->header;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
chrec_not_analyzed_yet = NULL_TREE;
chrec_dont_know = make_node (SCEV_NOT_KNOWN);
chrec_known = make_node (SCEV_KNOWN);
- TREE_TYPE (chrec_dont_know) = NULL_TREE;
- TREE_TYPE (chrec_known) = NULL_TREE;
+ TREE_TYPE (chrec_dont_know) = void_type_node;
+ TREE_TYPE (chrec_known) = void_type_node;
}
}
}
/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
- its BASE and STEP if possible. */
+ its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we
+ want STEP to be invariant in LOOP. Otherwise we require it to be an
+ integer constant. */
bool
-simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step)
+simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step,
+ bool allow_nonconstant_step)
{
basic_block bb = bb_for_stmt (stmt);
tree type, ev;
return false;
*step = CHREC_RIGHT (ev);
- if (TREE_CODE (*step) != INTEGER_CST)
+ if (allow_nonconstant_step)
+ {
+ if (tree_contains_chrecs (*step, NULL)
+ || chrec_contains_symbols_defined_in_loop (*step, loop->num))
+ return false;
+ }
+ else if (TREE_CODE (*step) != INTEGER_CST)
return false;
+
*base = CHREC_LEFT (ev);
- if (tree_contains_chrecs (*base)
+ if (tree_contains_chrecs (*base, NULL)
|| chrec_contains_symbols_defined_in_loop (*base, loop->num))
return false;
void
scev_analysis (void)
{
- varray_type exit_conditions;
+ VEC(tree,heap) *exit_conditions;
- VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions");
+ exit_conditions = VEC_alloc (tree, heap, 37);
select_loops_exit_conditions (current_loops, &exit_conditions);
if (dump_file && (dump_flags & TDF_STATS))
- analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions);
+ analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
- number_of_iterations_for_all_loops (exit_conditions);
- VARRAY_CLEAR (exit_conditions);
+ number_of_iterations_for_all_loops (&exit_conditions);
+ VEC_free (tree, heap, exit_conditions);
}
/* Finalize the scalar evolution analysis. */
BITMAP_FREE (already_instantiated);
}
+/* Replace ssa names for that scev can prove they are constant by the
+ appropriate constants. Most importantly, this takes care of final
+ value replacement.
+
+ We only consider SSA names defined by phi nodes; rest is left to the
+ ordinary constant propagation pass. */
+
+void
+scev_const_prop (void)
+{
+ basic_block bb;
+ tree name, phi, type, ev;
+ struct loop *loop;
+ bitmap ssa_names_to_remove = NULL;
+
+ if (!current_loops)
+ return;
+
+ FOR_EACH_BB (bb)
+ {
+ loop = bb->loop_father;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ name = PHI_RESULT (phi);
+
+ if (!is_gimple_reg (name))
+ continue;
+
+ type = TREE_TYPE (name);
+
+ if (!POINTER_TYPE_P (type)
+ && !INTEGRAL_TYPE_P (type))
+ continue;
+
+ ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
+ if (!is_gimple_min_invariant (ev)
+ || !may_propagate_copy (name, ev))
+ continue;
+
+ /* Replace the uses of the name. */
+ replace_uses_by (name, ev);
+
+ if (!ssa_names_to_remove)
+ ssa_names_to_remove = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
+ }
+ }
+
+ /* Remove the ssa names that were replaced by constants. We do not remove them
+ directly in the previous cycle, since this invalidates scev cache. */
+ if (ssa_names_to_remove)
+ {
+ bitmap_iterator bi;
+ unsigned i;
+
+ EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
+ {
+ name = ssa_name (i);
+ phi = SSA_NAME_DEF_STMT (name);
+
+ gcc_assert (TREE_CODE (phi) == PHI_NODE);
+ remove_phi_node (phi, NULL);
+ }
+
+ BITMAP_FREE (ssa_names_to_remove);
+ scev_reset ();
+ }
+}
OSDN Git Service
