+ scalar_evolution_info = NULL;
+}
+
+/* Returns true if the expression EXPR is considered to be too expensive
+ for scev_const_prop. */
+
+bool
+expression_expensive_p (tree expr)
+{
+ enum tree_code code;
+
+ if (is_gimple_val (expr))
+ return false;
+
+ code = TREE_CODE (expr);
+ if (code == TRUNC_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == ROUND_DIV_EXPR
+ || code == TRUNC_MOD_EXPR
+ || code == CEIL_MOD_EXPR
+ || code == FLOOR_MOD_EXPR
+ || code == ROUND_MOD_EXPR
+ || code == EXACT_DIV_EXPR)
+ {
+ /* Division by power of two is usually cheap, so we allow it.
+ Forbid anything else. */
+ if (!integer_pow2p (TREE_OPERAND (expr, 1)))
+ return true;
+ }
+
+ switch (TREE_CODE_CLASS (code))
+ {
+ case tcc_binary:
+ case tcc_comparison:
+ if (expression_expensive_p (TREE_OPERAND (expr, 1)))
+ return true;
+
+ /* Fallthru. */
+ case tcc_unary:
+ return expression_expensive_p (TREE_OPERAND (expr, 0));
+
+ default:
+ return true;
+ }
+}
+
+/* Replace ssa names for that scev can prove they are constant by the
+ appropriate constants. Also perform final value replacement in loops,
+ in case the replacement expressions are cheap.
+
+ We only consider SSA names defined by phi nodes; rest is left to the
+ ordinary constant propagation pass. */
+
+unsigned int
+scev_const_prop (void)
+{
+ basic_block bb;
+ tree name, type, ev;
+ gimple phi, ass;
+ struct loop *loop, *ex_loop;
+ bitmap ssa_names_to_remove = NULL;
+ unsigned i;
+ loop_iterator li;
+ gimple_stmt_iterator psi;
+
+ if (number_of_loops () <= 1)
+ return 0;
+
+ FOR_EACH_BB (bb)
+ {
+ loop = bb->loop_father;
+
+ for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
+ {
+ phi = gsi_stmt (psi);
+ 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. */
+ if (name != ev)
+ 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;
+
+ EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
+ {
+ gimple_stmt_iterator psi;
+ name = ssa_name (i);
+ phi = SSA_NAME_DEF_STMT (name);
+
+ gcc_assert (gimple_code (phi) == GIMPLE_PHI);
+ psi = gsi_for_stmt (phi);
+ remove_phi_node (&psi, true);
+ }
+
+ BITMAP_FREE (ssa_names_to_remove);
+ scev_reset ();
+ }
+
+ /* Now the regular final value replacement. */
+ FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
+ {
+ edge exit;
+ tree def, rslt, niter;
+ gimple_stmt_iterator bsi;
+
+ /* If we do not know exact number of iterations of the loop, we cannot
+ replace the final value. */
+ exit = single_exit (loop);
+ if (!exit)
+ continue;
+
+ niter = number_of_latch_executions (loop);
+ if (niter == chrec_dont_know)
+ continue;
+
+ /* Ensure that it is possible to insert new statements somewhere. */
+ if (!single_pred_p (exit->dest))
+ split_loop_exit_edge (exit);
+ bsi = gsi_after_labels (exit->dest);
+
+ ex_loop = superloop_at_depth (loop,
+ loop_depth (exit->dest->loop_father) + 1);
+
+ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
+ {
+ phi = gsi_stmt (psi);
+ rslt = PHI_RESULT (phi);
+ def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+ if (!is_gimple_reg (def))
+ {
+ gsi_next (&psi);
+ continue;
+ }
+
+ if (!POINTER_TYPE_P (TREE_TYPE (def))
+ && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
+ {
+ gsi_next (&psi);
+ continue;
+ }
+
+ def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
+ def = compute_overall_effect_of_inner_loop (ex_loop, def);
+ if (!tree_does_not_contain_chrecs (def)
+ || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
+ /* Moving the computation from the loop may prolong life range
+ of some ssa names, which may cause problems if they appear
+ on abnormal edges. */
+ || contains_abnormal_ssa_name_p (def)
+ /* Do not emit expensive expressions. The rationale is that
+ when someone writes a code like
+
+ while (n > 45) n -= 45;
+
+ he probably knows that n is not large, and does not want it
+ to be turned into n %= 45. */
+ || expression_expensive_p (def))
+ {
+ gsi_next (&psi);
+ continue;
+ }
+
+ /* Eliminate the PHI node and replace it by a computation outside
+ the loop. */
+ def = unshare_expr (def);
+ remove_phi_node (&psi, false);
+
+ def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE,
+ true, GSI_SAME_STMT);
+ ass = gimple_build_assign (rslt, def);
+ gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
+ }
+ }
+ return 0;