ChangeLog.lno   [plain text]

APPLE LOCAL file lno
2004-07-18  Sebastian Pop  <>

	Merge from mainline (lno-merge-20040718).

2004-07-17  Zdenek Dvorak  <>

	* (tree-cfg.o): Add CFGLAYOUT_H dependency.
	* loop-init.c (loop_optimizer_init, loop_optimizer_finalize): Do not
	free the dominators.
	* passes.c (rest_of_handle_loop2): Free the dominators.
	* sched-rgn.c (compute_trg_info): Initialize fields of variable el.
	* tree-cfg.c: Include cfglayout.h.
	(tree_duplicate_bb): Copy also phi nodes.
	(struct ssa_name_map_entry): New type.
	(collect_defs, add_phi_args_after_copy, ssa_name_map_entry_hash,
	ssa_name_map_entry_eq, allocate_ssa_names,
	rewrite_to_new_ssa_names_def, rewrite_to_new_ssa_names_use,
	rewrite_to_new_ssa_names, tree_duplicate_sese_region): New functions.
	* tree-flow.h (tree_duplicate_sese_region): Declare.
	* tree-ssa-loop-ch.c (mark_defs_for_rewrite, duplicate_blocks): Removed.
	(copy_loop_headers): Use tree_duplicate_sese_region.
	* tree-ssa-loop-manip.c (copy_phi_nodes): Only copy the phi node
	* tree-ssa-pre.c (gate_pre): Disable the optimization.

2004-07-14  Dorit Naishlos <>

        * tree-vectorizer.c (vect_is_simple_use): Additional argument.
        (vect_is_supportable_op): Call vect_is_simple_use with extra argument.
        (vect_is_supportbale_store): Likewise.
        (vect_is_supportbale_assignment): Likewise.
        (vect_mark_stmts_to_be_vectorized): Cleanup - use vect_is_simple_use.
        (vect_get_vec_def_for_operand): Cleanup.

        (vect_analyze_data_refs): Support certain forms of COMPONENT_REF as
        array_base. Use force_gimple in handling of data-refs.
        (vect_force_dr_alignment_p): Support certain forms of COMPONENT_REF.
        (vect_align_data_ref): Likewise.
        (vect_analyze_data_ref_dependence): Likewise.

        (vect_analyze_operations): Remove duplicate calls to vect_debug_details.
        (vect_analyze_scalar_cycles): Likewise.
        (vect_analyze_data_ref_dependence): Likewise.
        (vect_analyze_data_refs_alignment): Likewise.
        (vect_analyze_pointer_ref_access): Likewise.
        (vect_analyze_pointer_ref_access): Likewise.
        (vect_analyze_data_refs): Likewise.
        (vect_analyze_loop_form): Likewise.

2004-07-13  Sebastian Pop  <>

	* tree-data-ref.c: Fix some comments for inclusion in mainline.
	(tree_fold_gcd): Moved...
	* tree.c (tree_fold_gcd):
	* tree.h (tree_fold_gcd): Declared here.

2004-07-13  Zdenek Dvorak  <>

	* tree-ssa-loop-niter.c (mark_maybe_infinite_loops): Handle abnormal

2004-07-13  Zdenek Dvorak  <>

	* (tree-ssa-loop.o, tree-ssa-dce.o): Add function.h
	* builtins.c (expand_builtin): Handle BUILT_IN_MAYBE_INFINITE_LOOP.
	* builtins.def (BUILT_IN_MAYBE_INFINITE_LOOP): New builtin.
	* function.h (struct function): Add marked_maybe_inf_loops field.
	* timevar.def (TV_MARK_MILOOPS): New timevar.
	* tree-flow.h (mark_maybe_infinite_loops): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add
	* tree-pass.h (pass_mark_maybe_inf_loops): Declare.
	* tree-ssa-dce.c: Include function.h.
	(find_obviously_necessary_stmts): Mark back edges only if they were
	not marked already.
	(perform_tree_ssa_dce): Do not call mark_dfs_back_edges here.
	* tree-ssa-loop-niter.c (unmark_surely_finite_loop,
	mark_maybe_infinite_loops): New functions.
	* tree-ssa-loop.c: Include function.h.
	(tree_mark_maybe_inf_loops, gate_tree_mark_maybe_inf_loops,
	pass_mark_maybe_inf_loops): New pass.
	* tree-ssa-operands.c (function_ignores_memory_p): Add

2004-07-12  Sebastian Pop  <>

	* (tree-scalar-evolution.o): Remove dependences on 
	tree-vectorizer.h and tree-data-ref.h. 
	(tree-data-ref.o): Add dependence on lambda.h.
	* lambda-trans.c, lambda.h: Add missing copyright notice.
	* tree-scalar-evolution.c: Don't include tree-data-ref.h and 
	tree-vectorizer.h.  Fix some comments.
	* tree-scalar-evolution.h (simple_iv): Modified to match the
	declaration that is in mainline.

2004-07-11  Dorit Naishlos <>

        * tree-vectorizer.c: Update documentation. Use '#ifdef
        ENABLE_CHECKING' to guard checks that are expected to have been
        verified during analysis. Use vect_debug_details/vect_debug_stats
        for dumping information.

        * tree-vectorizer.h (struct _stmt_vec_info): New field "memtag".
        (STMT_VINFO_MEMTAG): Access macro for new field "memtag".
        * tree-vectorizer.c (vect_create_data_ref): Get tag from new field.
        (vect_analyze_data_refs): Record the tag in the new memtag field.

        (vect_align_data_ref): Remove unused argument.
        (vect_analyze_data_refs): Call vect_align_data_ref with one argument.
        (vect_get_array_first_index): Additional argument to return the
        index rather than as the return value of the function.
        (create_index_for_array_ref): Call vect_get_array_first_index with
        an extra argument.
        (vect_create_data_ref): Remove unused argument.
        (vect_debug_stats, vect_debug_details): Argument "string" removed.

        (vect_analyze_pointer_ref_access): New function.
        (vect_analyze_data_refs): Call vect_analyze_pointer_ref_access.

        (vect_finish_stmt_generation): New function.
        (vect_transform_assignment, vect_transform_op, vect_transform_store):
        (vect_transform_load): Call vect_finish_stmt_generation.

        (get_vectype_for_scalar_type): No need to iterate through the
        different modes - build_vector_type already does that.

        (vect_transform_loop_bound): Check which edge is actually the 'then'.

        (vect_analyze_operations): Temporarily disable vectorization of loops
        with unknown loop bound.
2004-07-10  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (determine_biv_step): Use simple_iv.

2004-07-09  Devang Patel  <>

	* (tree-ssa-loop-manip.o): Add tree-scalar-evolution.h
	* tree-scalar-evolution.c (scev_rest): Check scalar_evolution_info
	and current_loops.
	* tree-ssa-loop-manip.c (tree-scalar-evolution.h): Include.
	(tree_duplicate_loop_to_header_edge): scev_reset () in the end.

2004-07-09  Steven Bosscher  <>,
	    Zdenek Dvorak  <>

	* tree-ssa-pre.c: Merge changes from mainline.

2004-07-09  Steven Bosscher  <>

	* varray.h (varray_data_enum): Remove VARRAY_DATA_DG.

2004-07-08  Sebastian Pop  <>

	* varray.c (element): Don't include dependence_node_def.

2004-07-08  Sebastian Pop  <>

	* (OBJS-common): Remove tree-dg.o.
	(tree-dg.o): Removed.
	(GTFILES): Remove tree-dg.h.
	* gengtype.c (open_base_files): Remove tree-dg.h.
	* tree-data-ref.c (subscript_dependence_tester): Don't define.
	(dump_data_dependence_relation): Print data references only
	when they are not NULL.
	(analyze_array_top): Removed.
	(initialize_data_dependence_relation): Is extern now.
	When the data references are NULL the relation is not known.
	(compute_affine_dependence): Is extern now.
	(find_data_references_in_loop): Returns chrec_dont_know when
	failing to analyze a difficult case.  
	(compute_data_dependences_for_loop): Terminate earlier when 
	find_data_references_in_loop fails.
	* tree-data-ref.h (data_dependence_relation): Update comments.
	(initialize_data_dependence_relation, compute_affine_dependence): 
	Declared extern.
	* tree-dg.c, tree-dg.h: Removed.
	* tree-flow-inline.h (dg_node_for_stmt): Removed.
	* tree-flow.h: Don't include tree-dg.h.
	(stmt_ann_d): Remove dependence_node field.
	* tree-ssa-loop.c: Include tree-data-ref.h.
	(tree_vectorize, tree_linear_transform): Don't construct the dg_graph.
	* tree-vectorizer.c: Remove some declarations of static functions.
	(vect_analyze_data_ref_dependence): Extra parameter for the vectorized 
	loop.  Don't rely on the information provided by the data
	reference structure.  Compute directly the relation between
	the data references instead of querying this information in
	the dg_graph.
	(vect_analyze_data_ref_dependences): Pass to
	vect_analyze_data_ref_dependence the information about the
	vectorized loop.
	* varray.h (varray_data_tag): Remove dependence_node_def.

2004-07-07  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (cand_value_at): Handle types correctly.
	(may_eliminate_iv): Verify there is no overflow.

2004-07-07  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (find_bivs, find_givs_in_stmt_scev):
	Ensure that step of the iv satisfies cst_and_fits_in_hwi.
	(determine_use_iv_cost_outer): Preserve the fact that the cost
	is infinity.
	* tree-ssa-loop-prefetch.c (WRITE_CAN_USE_READ_PREFETCH,
	(struct mem_ref_group): Type of step changed to HOST_WIDE_INT.
	(struct mem_ref): Type of delta changed to HOST_WIDE_INT.
	(dump_mem_ref, find_or_create_group, record_ref,
	struct ar_data, idx_analyze_ref, analyze_ref,
	gather_memory_references_ref, issue_prefetch_ref): Updated to reflect
	(ddown): New function.
	(prune_ref_by_self_reuse, prune_ref_by_group_reuse):
	(prune_ref_by_reuse): Use WRITE_CAN_USE_READ_PREFETCH and
	(prune_group_by_reuse): Add dumps.
	(issue_prefetch_ref): Assert that PREFETCH_BLOCK is a power of 2.
	* tree.c (cst_and_fits_in_hwi): Update comment and fix semantics.
	(int_cst_value, build_int_cst): Check that we use them only for
	types representable in HOST_WIDE_INT.

2004-07-07  Zdenek Dvorak  <>

	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
	Remove bogus check for chrec_contains_undetermined.

2004-07-06  Sebastian Pop  <>

	* basic-block.h (edge_source, edge_destination): Removed.
	* cfgloop.c (superloop_at_depth): Fix comment.
	* cfgloop.h (loop_from_num, outer_loop, inner_loop, next_loop, 
	loop_num, loop_depth, loop_header, loop_nb_iterations, 
	loop_num_exits, loop_exit_edges, loop_exit_edge): Removed.
	* lambda-code.c, tree-cfg.c, tree-data-ref.c, tree-dg.c, 
	tree-elim-check.c, tree-scalar-evolution.c, tree-ssa-dom.c, 
	tree-ssa-loop-ivcanon.c, tree-vectorizer.c: Inline removed functions.
	* tree-data-ref.c: Rewrite some comments.
	* tree-flow-inline.h (loop_of_stmt): Renamed loop_containing_stmt.

2004-07-04  Dorit Naishlos <>

	* tree-vectorizer.c (vect_create_data_ref, vect_init_vector): 
	Use insert_on_edge to add code in loop preheader.
	(vect_transform_loop): Make sure there's a preheader BB.

2004-06-30  Zdenek Dvorak  <>

	* tree-ssa-loop-prefetch.c: New file.
	* (tree-ssa-loop-prefetch.o): Add.
	* timevar.def (TV_TREE_PREFETCH): New.
	* tree-flow.h (tree_ssa_prefetch_arrays,
	standard_iv_increment_position): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add
	* tree-pass.h (pass_loop_prefetch): Declare.
	* tree-ssa-loop-ivcanon.c (estimate_loop_size): Force the size to be
	* tree-ssa-loop-ivopts.c (cst_and_fits_in_hwi): Moved to tree.c.
	(standard_iv_increment_position): New function.
	(zero_p): Export.
	* tree-ssa-loop-niter.c (zero_p): Remove duplicate function.
	* tree-ssa-loop.c (tree_ssa_loop_prefetch,
	gate_tree_ssa_loop_prefetch): New functions.
	(pass_loop_prefetch): New pass structure.
	* tree-ssa-operands.c (function_ignores_memory_p): New function.
	(get_expr_operands): Use it.
	* tree.c (cst_and_fits_in_hwi): Moved from tree-ssa-loop-ivopts.c.
	* tree.h (zero_p, cst_and_fits_in_hwi): Declare.

2004-06-28  Daniel Berlin  <>

	* lambda-code.c (print_linear_expression): Rename a few variables,
	simplify some code.
	(print_lambda_loop): Ditto.
	(lambda_compute_auxillary_space): Update a comment.
	(gcc_loop_to_lambda_loop): Update code for chrec_dont_know change.
	(struct dir_dist_pair): New.
	(reverse_dep): Ditto.
	(lambda_dep_mult_constant): New function.	
	(lambda_dep_add): Ditto.
	(lambda_vec_distdirvec_mult): Ditto.
	(lambda_vec_distdirmat_mult): Ditto.
	(lambda_deps_positive): Ditto.
	(lambda_transform_legal_p): Ditto.
	* lambda-mat.c (lambda_matrix_mult): Cleanup
	(lambda_matrix_delete_rows): Ditto.
	(lambda_matrix_row_add): Ditto.
	(lambda_matrix_col_exchange): Ditto.
	(lambda_trans_matrix_is_nonsingular): Rename to standard gcc predicate
	(lambda_trans_matrix_is_fullrank): Ditto.
	(lambda_trans_matrix_base): Rename to reflect actual computation.
	* lambda.h (lambda_transform_legal_p): Add prototype.
	* tree-loop-linear.c (linear_transform_loops): Rewrite a bit, use legality
	tester to test transforms.

2004-06-28  Daniel Berlin  <>

	* tree-data-ref.c (build_classic_dist_vector): Add argument, stop 
	making out-of-bounds array accesses when analyzing less than
	all the loops.  Add checks to verify.
	(build_classic_dir_vector): Ditto.
	(compute_data_dependences_for_loop): Pass in starting loop number
	to build_classic_*.

2004-06-27  Sebastian Pop  <>

	* tree.def (INTERVAL_CHREC): Removed.
	* tree-pretty-print.c (dump_generic_node): Handle SCEV_KNOWN and 
	* tree-chrec.h (build_polynomial_chrec): When one of the
	operands is chrec_dont_know, return directly chrec_dont_know.
	* tree-scalar-evolution.c (instantiate_parameters_1): Same.
	(initialize_scalar_evolutions_analyzer): Build chrec_dont_know using a  
	SCEV_NOT_KNOWN node, and chrec_known with a SCEV_KNOWN node.
2004-06-24  Sebastian Pop  <>

	* tree-chrec.c (chrec_fold_automatically_generated_operands, 
	Use chrec_dont_know instead of a call to chrec_contains_undetermined.
	(tree_fold_factorial, tree_fold_binomial, chrec_evaluate): Resurrect.
	(chrec_apply): Reinsert the cases that were removed.
	(chrec_convert): Remove the check for NULL_TREE inserted two days ago.
	* tree-scalar-evolution.c (follow_ssa_edge_in_rhs): As a sequel of 
	removing the tree_fold_* functions, the analyzed trees can contain 
	NON_LVALUE_EXPR nodes.  Use STRIP_TYPE_NOPS for avoiding these nodes.
	(number_of_iterations_in_loop): Add the missing open parenthesis in 
	the debugging dumps.
	(initialize_scalar_evolutions_analyzer): Use an INTERVAL_CHREC for 
	constructing the chrec_dont_know node.  This fixes some strange 
	problems that arise when chrec_dont_know is an INTEGER_CST. 
	* tree.def (INTERVAL_CHREC): Resurrect.

2004-06-23  Zdenek Dvorak  <>

	* tree-chrec.c (chrec_merge): Handle case when one of the arguments
	was not analyzed yet correctly.

2004-06-23  Sebastian Pop  <>
	* tree-chrec.c (chrec_fold_automatically_generated_operands): Now
	static.  Clean comments.
	(hide_evolution_in_loop, chrec_merge_types): Removed.  
	* tree-chrec.h (hide_evolution_in_loop,
	chrec_fold_automatically_generated_operands): Remove declarations.
	* tree-scalar-evolution.c: Remove an old part of the comment at the 
	beginning of the file.
	compute_overall_effect_of_inner_loop, add_to_evolution_1,
	analyze_scalar_evolution_1, analyze_scalar_evolution): Test for 
	chrec_dont_know instead of calling chrec_contains_undetermined.
2004-06-22  Dorit Naishlos <>

	* tree-vectorizer.c (vect_create_data_ref): Fix setting of mem_tag.
	(vect_analyze_data_refs): Make sure we have a mem_tag.

2004-06-22  Sebastian Pop  <>

	* tree-fold-const.c, tree-fold-const.h: Removed.
	* (SCEV_H, tree-chrec.o): Remove tree-fold-const.h.
	(OBJS-common): Remove tree-fold-const.o.
	(tree-fold-const.o): Removed.
	* gengtype.c (open_base_files): Remove tree-fold-const.h.
	* lambda-code.c, tree-chrec.c, tree-data-ref.c, tree-dg.c, 
	tree-elim-check.c, tree-loop-linear.c, tree-pretty-print.c, 
	tree-scalar-evolution.c, tree-ssa-loop-ivcanon.c, 
	tree-ssa-loop-ivopts.c, tree-ssa-loop-niter.c, tree-vectorizer.c: 
	Don't include tree-fold-const.h.
	* tree-chrec.c, tree-data-ref.c: Replace uses of tree_fold_* with 
	fold (build (*, ...))
	* tree-data-ref.c (tree_fold_gcd, tree_fold_divides_p,
	tree_fold_bezout): Saved from deletion here.
2004-06-22  Sebastian Pop  <>

	* tree-chrec.c, tree-chrec.h, tree-data-ref.c, tree-dg.c, 
	tree-elim-check.c, tree-scalar-evolution.c, tree-ssa-loop-niter.c, 
	tree-vectorizer.c: Replace chrec_top with chrec_dont_know, 
	and chrec_bot with chrec_known.  Replace the checks of chrec_top 
	with calls to chrec_contains_undetermined.
	* tree.def (INTERVAL_CHREC): Removed.  
	* cfgloop.h (loop): Update comments around nb_iterations field.  
	* lambda-code.c (gcc_loop_to_lambda_loop): Always check for 
	undetermined chrec after calling number_of_iterations_in_loop.
	* tree-chrec.c (chrec_fold_multiply_ival_cst, 
	chrec_merge_types, chrec_contains_intervals, chrec_evaluate, 
	chrec_merge_intervals): Removed.
	(chrec_fold_plus_1, chrec_fold_plus, chrec_fold_minus, 
	chrec_fold_multiply, chrec_merge, 
	evolution_function_is_affine_multivariat, chrec_convert): 
	Remove uses of INTERVAL_CHREC nodes.
	(chrec_apply): Classify as unknown all the non-affine cases.
	* tree-fold-const.h (tree_fold_binomial): Removed.
	* tree-chrec.h (CHREC_LOW, CHREC_UP, 
	chrec_contains_intervals, build_interval_chrec, 
	build_chrec_top_type, evolution_function_is_multivariate, 
	chrec_should_remain_symbolic): Removed.
	(tree_is_chrec, chrec_zerop, evolution_function_is_affine_p): 
	Remove uses of INTERVAL_CHREC nodes.
	* tree-data-ref.c (analyze_ziv_subscript, 
	analyze_overlapping_iterations): Same.
	* tree-pretty-print.c (dump_generic_node): Same.
	* tree-scalar-evolution.c (chrec_is_positive, 
	instantiate_parameters_1, gather_chrec_stats, 
	initialize_scalar_evolutions_analyzer): Same.
	(analyze_scalar_evolution_in_loop): Make it static.
	(resolve_mixers): Fix comments.
	(chrec_stats, reset_chrecs_counters, dump_chrecs_stats):
	Remove nb_interval_chrec counter.
	(chrec_is_positive, simple_iv): Always check for undetermined after 
	a call to number_of_iterations_in_loop or analyze_scalar_evolution.
	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables, 
	canonicalize_loop_induction_variables): Same.
	* tree-ssa-loop-ivopts.c (determine_biv_step): Same.
	* tree-ssa-loop-niter.c (find_loop_niter_by_eval): Same.
	(estimate_numbers_of_iterations_loop): Remove redundant call to 
	* tree-scalar-evolution.h (analyze_scalar_evolution_in_loop): 
	Remove declaration, the function is now static.
	* tree-vectorizer.c (vect_analyze_loop_with_symbolic_num_of_iters):
	Don't test for INTERVAL_CHREC nodes.

2004-06-22  Devang Patel  <>
        PR 16105	
        * tree-vectorizer.c (vect_analyze_operations): Type of MODIFY_EXPR is
        not reliable. Use LHS's type.

2004-06-21  Zdenek Dvorak  <>

	PR rtl-optimization/16001
	* loop-iv.c (iv_number_of_iterations): Prevent copy propagation in

2004-06-21  Sebastian Pop  <>

	* tree.def (PEELED_CHREC): Removed.
	* tree-chrec.c (is_not_constant_evolution, chrec_fold_plus_1, 
	chrec_fold_multiply, chrec_replace_initial_condition, chrec_convert):
	Don't handle PEELED_CHREC nodes.
	(chrec_fold_plus_peel_cst, chrec_fold_plus_poly_peel, 
	chrec_fold_plus_peel_poly, chrec_fold_plus_peel_peel, 
	chrec_fold_multiply_peel_cst, chrec_fold_multiply_poly_peel, 
	chrec_fold_multiply_peel_peel, simplify_peeled_chrec): Removed.
	* tree-chrec.h (tree_is_chrec): Don't handle PEELED_CHREC nodes.
	(build_peeled_chrec, evolution_function_is_peeled_affine_p): Removed.
	* tree-pretty-print.c (dump_generic_node): Don't handle
	* tree-scalar-evolution.c (analyze_evolution_in_loop,
	instantiate_parameters_1): Same.
	(chrec_stats, reset_chrecs_counters, dump_chrecs_stats, 
	gather_chrec_stats): Don't count the number of PEELED_CHREC nodes.

2004-06-18  Sebastian Pop  <>

	* (OBJS-common): Remove tree-elim-check.o.
	* tree-scalar-evolution.c (first_iteration_non_satisfying_noev_noev, 
	first_iteration_non_satisfying): Removed.
	(number_of_iterations_in_loop): Clean up.
	* tree-scalar-evolution.h (first_iteration_non_satisfying): Removed.
	* tree-ssa-loop-ivopts.c (zero_p): Compare tree pointer
	against NULL_TREE.
	* tree-ssa-loop.c (tree_ssa_loop_test): Return when loops
	structure is not available.
	(tree_elim_checks): Disabled for the moment.  Don't call

2004-06-17  Andrew MacLeod  <>

	* tree-cfg.c (tree_make_forwarder_block):  Use SET_PHI_RESULT.
	* tree-flow-inline.h (get_use_op_ptr):  Return a use_operand_p.
	(get_use_from_ptr, get_def_from_ptr):  New.  Return operand pointers.
	(get_def_op_ptr):  Return a def_operand_p instead of a 'tree *'.
	(get_v_may_def_result_ptr):  Return a def_operand_p.
	(get_v_may_def_op_ptr, get_vuse_op_ptr):   Return a use_operand_p.
	(get_v_must_def_op_ptr):  Return a def_operand_p.
	(get_phi_result_ptr):  New.  Return a pointer to the result of a PHI.
	(get_phi_arg_def_ptr):  New.  Return a pointer to an argument of a PHI.
	(phi_element_for_edge):  Remove.
	* tree-flow.h (propagate_value, replace_exp):  Change prototype.
	(propagate_tree_value):  Add new prototype.
	(phi_element_for_edge):  Remove prototype.
	* tree-into-ssa.c (mark_def_sites):  Use new operand types.
	(prepare_operand_for_rename):  Split into two functions.
	(prepare_use_operand_for_rename):  Prepare use operands.
	(prepare_def_operand_for_rename):  Prepare def operands.
	(rewrite_stmt):  Use new operand types.
	(rewrite_operand):  Use new operand types, change parameter type.
	* tree-outof-ssa.c (replace_variable):  Split into two functions.
	(replace_use_variable):  Rewrite uses.
	(replace_def_variable):  Rewrite defs.
	(rewrite_trees, rewrite_vars_out_of_ssa):  Use new operand types.
	* tree-phinodes.c (make_phi_node, resize_phi_node):  Use new types.
	(add_phi_arg, remove_phi_arg_num):  Use new operand types.
	* tree-ssa-ccp.c (substitute_and_fold):  Use new operand types.
	(ccp_fold, replace_uses_in):  Use new operand types.
	* tree-ssa-copy.c (replace_ssa_names):  Rename to replace_ssa_names_ann
	and no longer set the value, change parameter type.
	(replace_exp_1):  Use new operand types.
	(propagate_value):  Change parameter type, use new operand types.
	(propagate_tree_value):  Propagate_value without SSA operands.
	(replace_exp, cprop_operand, cprop_into_stmt):  Use new operand types.
	(cprop_into_successor_phis):  Use new operand types.
	* tree-ssa-dom.c (thread_across_edge):  Use new operand types.
	(eliminate_redundant_computations):  Use new operand types.
	* tree-ssa-dse.c (fix_phi_uses):  Use new operand_types.
	(fix_stmt_v_may_defs):  Use new operand_types.
	* tree-ssa-live.c (create_ssa_var_map):  Use new operand_types.
	(build_tree_conflict_graph):  Use new operand_types.
	* tree-ssa-loop.c (duplicate_blocks):  Use PHI_ARG_DEF_FROM_EDGE.
	* tree-ssa-operands.c (struct freelist_d):  Remove.
	(check_optype_freelist, add_optype_freelist):  Remove.
	(allocate_def_optype, allocate_use_optype, allocate_v_may_def_optype,
	allocate_vuse_optype, allocate_v_must_def_optype):  Call ggc_alloc.
	(free_uses, free_defs, free_vuses, free_v_may_defs, free_v_must_defs):
	Call ggc_free instead of add_optype_freelist.
	(init_ssa_operands, fini_ssa_operands):  Remove free list code.
	(finalize_ssa_defs, finalize_ssa_uses):  Set new use/def operands.
	* tree-ssa-operands.h (struct def_optype_d):  Change underlying type.
	(struct use_optype_d):  Change underlying type.
	(def_operand_p, use_operand_p):  New types for pointers to operands.
	V_MUST_DEF_OP):  Use new pointer type instead of dereferencing directly.
	(USE_FROM_PTR, DEF_FROM_PTR):  New macros to "dereference" operand 
	pointer types.
	(SET_USE, SET_DEF):  New macros to set operands from their pointer.
	SET_VUSE_OP, SET_V_MUST_DEF_OP): New SET routines for operands.
	(PHI_RESULT_PTR, PHI_RESULT, SET_PHI_RESULT):  Macros to manage the
	PHI result as an operand.
	PHI_ARG_DEF_PTR_FROM_EDGE):  Macros to manage the PHI arguments.
	* tree-ssa-pre.c (eliminate):  Call propagate_tree_value.
	* tree-tailcall.c (independent_of_stmt_p, propagate_through_phis):  Use
	* tree.h (PHI_RESULT):  Renamed to PHI_RESULT_TREE.

	* tree-ssa-loop-ivopts.c (find_bivs, mark_bivs,
	find_interesting_uses_outer_or_nonlin, find_interesting_uses_stmt,
	find_interesting_uses_outside, add_old_iv_candidates,
	remove_statement, rewrite_use_nonlinear_expr, split_loop_exit_edge,
	protect_loop_closed_ssa_form_use, compute_phi_arg_on_exit,
	rewrite_use_outer): Use new operand types.

2004-06-16  Dale Johannesen  <>

	* (GTFILES): Add tree-chrec.h.
	* tree-chrec.h (chrec_top, chrec_bot): Add GTY.
	* tree-scalar-evolution.c (initialize_scalar_evolutions_analyzer):
	Set chrec_top, chrec_bot once per compilation.
	* gengtype.c (ifiles):  Add tree-fold-const.h, tree-chrec.h.

2004-06-16  Dale Johannesen  <>
	* tree-flow.h (tree_ann_common-d.aux): Document required behavior.
	* tree-ssa-loop-manip.c (allocate_new_names): Don't propagate
	new_names into copies.

2004-06-16  Zdenek Dvorak  <>

	PR tree-optimization/15993
	* tree-ssa-dom.c (thread_across_edge): Do not thread edge if its
	destination is unchanged.

2004-06-14  Dorit Naishlos <>

	* tree-vectorizer.c (vect_analyze_data_refs): Minor fix.

2004-06-14  Andrew Pinski  <>

	* tree-ssa-return.c: Remove.
	* (OBJS-common): Remove tree-ssa-return.o
	(tree-ssa-return.o): Remove.
	* timevar.def (TV_TREE_RETURN): Remove.
	* tree-optimize.c (init_tree_optimization_passes):
	Do not run pass_return.
	* tree-pass.h (pass_return): Remove declaration.

2004-06-14  Dorit Naishlos <>

        * tree-data-ref.c (init_data_ref): New function.
        * tree-data-ref.h (init_data_ref): New function.
        * tree-vectorizer.c (vect_get_array_first_index): Return index instead
        of success status, and support pointers.
        (vect_create_index_for_array_ref): Remove ARRAY_REF restriction, and
        change call to vect_get_array_first_index.
        (vect_create_data_ref): Handle INDIRECT_REFs.
        (vect_is_supportable_store): Handle INDIRECT_REFs.
        (vect_is_supportable_load): Handle INDIRECT_REFs.
        (vect_analyze_data_ref_dependence): Handle INDIRECT_REFs.
        (vect_analyze_data_ref_dependences): Remove usage of variable 'ok'.
        (get_array_base): Removed (not used anymore).
        (vect_force_dr_alignment_p): Use DR_BASE_NAME instead of
        (vect_align_data_ref): Likewise.
        (vect_transform_store): Remove ARRAY_REF restriction.
        (vect_transform_load): Remove ARRAY_REF restriction.
        (vect_compute_data_ref_alignment): Support pointers.
        (vect_analyze_data_refs): Support pointers.

        (vect_debug_stats): New Function.
        (vect_debug_details): New Function.
        (vect_transform_loop): Use vect_debug_stats and vec_debug_details.
        (vect_analyze_loop): Use vect_debug_details.
        (vect_analyze_scalar_cycles): Use vect_debug_stats.
        (vect_analyze_data_ref_dependence): Likewse.
        (vect_analyze_data_refs_alignment): Likewise.
        (vect_analyze_data_ref_accesses): Likewise.
        (vect_analyze_data_refs): Likewise.
        (vect_analyze_loop_form): Likewise.

        (vect_gen_if_guard): Formatting fixes (avoid 80 column overflow).
        (vect_update_initial_conditions_of_duplicatd_loop): Likewise.
        (vect_transform_loop): Likewise.
        (vect_analyze_loop_form): Likewise.

2004-06-13  Zdenek Dvorak  <>

	Merge from mainline (lno-merge-20040612).

2004-06-13  Dorit Naishlos <>

	* tree-chrec.c (evolution_function_is_affine_multivariat): Add check
	* tree-dg.c (ddg_direction_between_stmts): Add check for chrec_top.

	* tree-pass.h (TODO_write_loop_closed): New to-do flag.
	* tree-optimize.c (execute_todo): Handle new to-do flag 
	* tree-ssa-loop.c (struct tree_opt_pass pass_vectorize): Set

	* tree-vectorizer.c (vect_transform_loop): Add calls to 
	(vect_analyze_data_ref_dependence): Fix last argument in call to 

2004-06-11  Zdenek Dvorak  <>

	PR target/15944
	* loop-invariant.c (may_assign_reg_p): Use can_copy_p.

2004-06-11  Olga Golovanevsky  <>
            Dorit Naishlos <>

        * tree-vectorizer.c (vect_generate_tmps_on_preheader):
        (vect_gen_if_guard): New functions.
        Update also phis of bb at the exit of epilog loop.
        (vect_transform_loop): Remove code that now belongs to
        vect_generate_tmps_on_preheader () function. Use
        vect_gen_if_guard function twice.

2004-06-10  Zdenek Dvorak  <>

	* tree-ssa-loop-ch.c: New file.
	* (tree-ssa-loop-ch.o): Add.
	(tree-ssa-loop.o): Add SCEV_H and tree-vectorizer.h dependency.
	* cfgloop.h (current_loops): Declare.
	* common.opt (fivcanon, fivopts, floop-test, ftree-lim): Add.
	(ftree-loop-optimize, fscalar-evolutions, fall-data-deps,
	ftree-ddg): Remove.
	* flags.h (flag_scalar_evolutions, flag_all_data_deps,
	flag_tree_loop, flag_ddg): Removed.
	(flag_tree_lim, flag_ivcanon, flag_ivopts,
	flag_tree_ssa_loop_test): New.
	(f_options): Remove scalar-evolutions, all-data-deps,
	tree-ddg, tree-loop-optimize.
	* toplev.c (flag_scalar_evolutions, flag_all_data_deps,
	flag_tree_loop, flag_ddg): Removed.
	(flag_tree_lim, flag_ivcanon, flag_ivopts,
	flag_tree_ssa_loop_test): New.
	* opts.c (decode_options, common_handle_option): Initialize new
	* timevar.def (TV_SCALAR_EVOLUTIONS, TV_ALL_DATA_DEPS): Removed.
	* tree-flow.h (test_unrolling_and_peeling, test_loop_versioning):
	(tree_unroll_loops_completely): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Reorganize loop
	optimizer passes.
	* tree-pass.h (pass_scev, pass_scev_init, pass_scev_anal,
	pass_scev_depend, pass_scev_linear_transform, pass_scev_iv_canon,
	pass_scev_elim_checks, pass_scev_vectorize, pass_scev_done, pass_ddg,
	pass_delete_ddg): Removed.
	(pass_loop_init, pass_loop_test, pass_lim, pass_unswitch,
	pass_iv_canon, pass_record_bounds, pass_elim_checks, pass_vectorize,
	pass_complete_unroll, pass_linear_transform, pass_iv_optimize,
	pass_loop_done): Declare.
	* tree-scalar-evolution.c (current_loops): Moved to tree-ssa-loop.c.
	(dd_info_available): Removed.
	(scev_init, scev_depend, scev_elim_checks, scev_vectorize, scev_done,
	gate_scev, gate_scev_analysis, gate_scev_depend, gate_scev_elim_checks,
	gate_scev_vectorize): Removed.
	(pass_scev, pass_scev_init, pass_scev_anal, pass_scev_depend,
	pass_scev_vectorize, pass_scev_linear_transform,
	pass_scev_iv_canon, pass_scev_elim_checks, pass_scev_done,
	pass_ddg, pass_delete_ddg): Removed.
	* tree-scalar-evolution.h (scev_analysis): Declare.
	(scev_analysis): Export.
	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
	Add parameter to control whether find_loop_niter_by_eval is run.
	(canonicalize_induction_variables): Do not unroll loops.
	(tree_unroll_loops_completely): Split from
	* tree-ssa-loop-ivopts.c (tree_ssa_iv_optimize_init,
	tree_ssa_iv_optimize_finalize, tree_ssa_iv_optimize,
	tree_ssa_iv_optimize): Global initialization/finalization removed.
	* tree-ssa-loop-manip.c (test_unrolling_and_peeling,
	test_loop_versioning): Removed.
	* tree-ssa-loop.c: Include tree-scalar-evolution.h and
	(current_loops): Moved from tree-scalar-evolution.c.
	(tree_ssa_loop_opt): Removed.
	(gate_loop): Removed.
	(pass_loop): Modified.
	(should_duplicate_loop_header_p, mark_defs_for_rewrite,
	duplicate_blocks, do_while_loop_p, copy_loop_headers,
	gate_ch, pass_ch): Moved to tree-ssa-loop-ch.c.
	(tree_ssa_loop_init, pass_loop_init, tree_ssa_loop_im,
	gate_tree_ssa_loop_im, pass_lim, tree_ssa_loop_unswitch,
	gate_tree_ssa_loop_unswitch, pass_unswitch, tree_ssa_loop_ivcanon,
	gate_tree_ssa_loop_ivcanon, pass_iv_canon, tree_ssa_loop_bounds,
	pass_record_bounds, tree_ssa_loop_test, pass_loop_test,
	tree_elim_checks, gate_tree_elim_checks, pass_elim_checks,
	tree_vectorize, gate_tree_vectorize, pass_vectorize,
	tree_complete_unroll, gate_tree_complete_unroll, pass_complete_unroll,
	tree_linear_transform, gate_tree_linear_transform,
	pass_linear_transform, tree_ssa_loop_ivopts, gate_tree_ssa_loop_ivopts,
	pass_iv_optimize, tree_ssa_loop_done, pass_loop_done): New.
	* testsuite/gcc.dg/tree-ssa-chrec/*: Updated.

2004-06-10  Sebastian Pop  <>

	* tree.def: Remove EXPONENTIAL_CHREC node.
	* tree-chrec.c (is_not_constant_evolution, chrec_fold_plus_1,
	chrec_fold_multiply, chrec_evaluate, chrec_apply,
	chrec_replace_initial_condition, initial_condition,
	hide_evolution_in_loop, hide_evolution_in_other_loops_than_loop,
	evolution_part_in_loop_num, reset_evolution_in_loop,
	reset_evolution_in_loop, chrec_merge, is_multivariate_chrec_rec,
	is_multivariate_chrec, evolution_function_is_affine_multivariate_p,
	evolution_function_is_univariate_p, chrec_convert): Don't
	handle EXPONENTIAL_CHREC nodes.
	(chrec_fold_plus_expo_cst, chrec_fold_plus_cst_expo,
	chrec_fold_plus_poly_expo, chrec_fold_plus_expo_poly,
	chrec_fold_plus_expo_expo, chrec_fold_multiply_poly_expo,
	chrec_fold_multiply_expo_expo, is_pure_sum_chrec): Removed.
	* tree-chrec.h (tree_is_chrec, evolution_function_is_affine_p):
	Don't handle EXPONENTIAL_CHREC nodes.
	(build_exponential_chrec): Removed.
	(no_evolution_in_loop_p): Use a call to tree_is_chrec for
	determining when a node represents a scalar evolution.
	* tree-data-ref.c (siv_subscript_p): Don't handle
	* tree-pretty-print.c (dump_generic_node): Same.
	* tree-scalar-evolution.c: Remove FIXME comments about
	EXPONENTIAL_CHREC nodes.  Add a pointer to the slides
	presented at the GCC Summit 2004 about the scalar evolutions.
	(compute_overall_effect_of_inner_loop): Clarify the leading comment.
	(chrec_is_positive, add_to_evolution_1, add_to_evolution,
	instantiate_parameters_1): Don't handle EXPONENTIAL_CHREC nodes.
	(multiply_evolution_1, multiply_evolution): Removed.
	(first_iteration_non_satisfying_ev_ev): Handle only affine
	(follow_ssa_edge_in_rhs): Cases that were detected as
	EXPONENTIAL_CHREC nodes are now mapped to the unknown element
	(be it top or bottom) called chrec_top.
	(chrec_stats, reset_chrecs_counters, dump_chrecs_stats,
	gather_chrec_stats): Don't count the EXPONENTIAL_CHREC nodes.
	* tree-vectorizer.c (vect_is_simple_iv_evolution,
	vect_analyze_loop_with_symbolic_num_of_iters): Use
	tree_is_chrec for determining whether the given node has an

2004-06-09  Zdenek Dvorak  <>

	PR middle-end/15876
	* tree-ssa-loop-ivopts.c (force_var_cost): Initialize DECL_RTL

2004-06-09  Zdenek Dvorak  <>

	* passes.c (rest_of_handle_loop2): Run loop optimizations always.

2004-06-09  Zdenek Dvorak  <>

	* ra-build.c (livethrough_conflicts_bb): Check also contains_call.

2004-06-09  Olga Golovanevsky  <>
            Dorit Naishlos <>

	* tree-vctorizer.c
	Handle general form of "init" and "step" of access function.
	* tree-ssa-loop-manip.c (tree_duplicate_loop_to_exit_cfg):
	The exit from loop is taken from bb previous to latch instead
	of latch itself.

2004-06-08  Andrew Pinski  <>

	PR tree-opt/15881
	* tree-scalar-evolution.c (count_ev_in_wider_type): Use
	fold_convert instead of convert.
	(compute_overall_effect_of_inner_loop): Likewise.
	(chrec_is_positive): Likewise.
	(add_to_evolution_1): Likewise.
	(add_to_evolution): Likewise.
	(first_iteration_non_satisfying_1): Likewise.
	(follow_ssa_edge_in_rhs): Likewise.
	(interpret_rhs_modify_expr): Likewise.
	(number_of_iterations_in_loop): Likewise.

2004-06-08  Zdenek Dvorak  <>

	PR tree-optimization/15779
	* tree-scalar-evolution.c (scev_initialize): Clean the nb_iterations
	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables): Do
	not clean nb_iterations field.

2004-06-07  Zdenek Dvorak  <>

	* version.c (version_string): Update "merged" stamp.

2004-05-30  Daniel Berlin  <>

	* tree-loop-linear.c (linear_transform_loops): We don't handle sibling
	loops, or loops with multiple exits, yet.
	* lambda-code.c (invariant_in_loop): Check outer loops too for
	right now.
	(lle_to_gcc_expression): Special case the coefficient == 1 cases.
	(lambda_loopnest_to_gcc_loopnest): Use correct test.

2004-05-30  Zdenek Dvorak  <>
	    Jeff Law  <>

	* tree-into-ssa.c (prepare_operand_for_rename): New argument is_use.
	If the operand is for a use, then strip away the SSA_NAME, do not
	strip away the SSA_NAME for a set.  Never call release_ssa_name.
	(mark_def_sites): Appropriately pass additional argument to
	prepare_operand_for_rename.  If a VDEF_RESULT is not an SSA_NAME,
	then set the VDEF_RESULT to the VDEF_OP.
	(set_def_block): Strip away any SSA_NAME to get to the real
	underlying variable.
	(ssa_mark_def_sites): Prevent set_def_block from doing so.

	* tree-ssa-loop.c (mark_defs_for_rewrite): Record defined ssa names.
	(duplicate_blocks): Use rewrite_ssa_into_ssa.
	(pass_ch): Remove TODO_rename_vars.

2004-05-30  Zdenek Dvorak  <>

	* opts.c (decode_options): Enable flag_scalar_evolutions by default.

2004-05-30  Zdenek Dvorak  <>

	* fold-const.c (fold_widened_comparison,
	fold_sign_changed_comparison): New.
	(fold): Use them.
	* tree-flow.h (struct tree_niter_desc): New field additional_info.
	* tree-ssa-loop-niter.c (simplify_using_outer_evolutions): Do not
	rewrite expressions in-place.
	(tree_simplify_using_condition, simplify_using_initial_conditions):
	New functions.
	(number_of_iterations_exit): Use simplify_using_initial_conditions.
	(struct nb_iter_bound): New field additional.
	(record_estimate, estimate_numbers_of_iterations_loop): Initialize
	field additional.
	(upper_bound_in_type, lower_bound_in_type): Export.  Handle
	unsigned->signed conversion correctly.
	(can_count_iv_in_wider_type): Pass the additional info to
	(can_count_iv_in_wider_type_bound): Use the additional info.
	* tree.h (lower_bound_in_type, upper_bound_in_type): Declare.
	* config/i386/i386.c (legitimate_constant_p): Do not allow
	integer - symbol.

2004-05-29  Sebastian Pop  <>

	* lambda-code.c: Spell check.
	* lambda-trans.c: Same.
	* tree-chrec.c: Same.
	* tree-dg.c: Same.
	* tree-loop-linear.c: Same.
	* tree-ssa-loop-im.c: Same.
	* tree-ssa-loop-ivcanon.c: Same.
	* tree-ssa-loop-ivopts.c: Same.
	* tree-ssa-loop-manip.c: Same.
	* tree-ssa-loop.c: Same.
	* tree-vectorizer.c: Same.

2004-05-28  Zdenek Dvorak  <>

	* tree-ssa-loop-niter.c (number_of_iterations_cond): Record correct

2004-05-28  Dale Johannesen  <>

	* loop-invariant.c (check_maybe_invariant):  Disallow hoisting CALLs.

2004-05-27  Sebastian Pop  <>

	Merge from mainline (lno-merge-20040526).
	* tree-scalar-evolution.c (draw_tree_cfg): Removed.
	* tree-into-ssa.c: Didn't merged

2004-05-25  Sebastian Pop  <>
            Dorit Naishlos <>

        * tree-scalar-evolution.c (first_iteration_non_satisfying_1):
        Include the evolution of the non varying chrec in other_evs.
        (number_of_iterations_in_loop): Don't instantiate the chrecs
        before the computation of loop counts.

2004-05-25  Olga Golovanevsky  <>
            Dorit Naishlos <>

        * tree-vectorizer.c (vect_transform_loop_bound): Advance IVs
        by correct amount.
        (vect_transform_loop, vect_build_symbl_bound): Use shifts
        instead of division/multiplication to advance IVs.

2004-05-25  Zdenek Dvorak  <>

	* tree-scalar-evolution.c (number_of_iterations_in_loop):
	Do not produce COND_EXPRs.

2004-05-25  Zdenek Dvorak  <>

	* tree-scalar-evolution.c (resolve_mixers): New function.
	(already_instantiated): Type changed to bitmap.
	(scev_initialize, scev_finalize): Reflect the change.
	(analyze_scalar_evolution_in_loop): Use resolve_mixers.
	(instantiate_parameters_1): Add possibility to just resolve mixers.
	Fold the results.
	(number_of_iterations_in_loop): Use number_of_iterations_exit.
	* tree-ssa-loop-niter.c (simplify_using_outer_evolutions): New
	(number_of_iterations_exit): Use it.

2004-05-24  Dale Johannesen  <>
	* loop-invariant.c (find_defs):  Add DF_EQUIV_NOTES.

2004-05-21  Zdenek Dvorak  <>

	* (tree-ssa-loop-manip.o): Add cfglayout.h dependency.
	* tree-flow.h (collect_defs, rename_variables_in_bb, rename_op,
	allocate_new_names, free_new_names): Declaration removed.
	(tree_duplicate_loop_to_exit): Declare.
	* tree-ssa-loop-manip.c: Include cfglayout.h.
	(collect_defs, rename_variables_in_bb, rename_op,
	allocate_new_names, free_new_names): Made static.
	(tdlte_rename_variables_in_loop, tdlte_copy_phi_nodes,
	tree_duplicate_loop_to_exit_cfg, tree_duplicate_loop_to_exit):
	Moved from tree-vectorizer.c.
	* tree-vectorizer.c (vect_duplicate_loopm vect_copy_phi_nodes,
	vect_rename_variables_in_loop, vect_tree_duplicate_loop): Moved
	to tree-ssa-loop-manip.c and renamed.

2004-05-20  Olga Golovanevsky  <>
            Dorit Naishlos <>

        * tree-vectorizer.c (vect_transform_loop): New parameter;
        if bound is unknown, duplicates loop before vectorizing.
        (vect_transfrom_loop_bound): New parameter; now deal with
        symbolic loop bound.
        (vect_duplicate_loop, vect_copy_phi_nodes)
        (vect_rename_variables_in_loop, vect_tree_split_edge)
        (vect_tree_duplicate_loop, vect_build_symbl_bound): New functions.
        (new_loop_vec_info): Initialize the new field loop_vec_info:
        * tree-vectorizer.h (loop_vec_info: symb_numb_of_iters): Added.
        * cfgloopmanip.c (duplicate_loop): Made non-static.
        * tree-ssa-loop-manip.c (collect_defs): Made non-static.
        (allocate_new_names): Made non-static. Added option to allocate
        for original loop or not.
        (rename_op): Made non-static. Added input check.
        (rename_variables_in_bb): Made mpm-static.
        original loop were also renamed.
        (free_new_names): release_ssa_name only if defs of original
        loop were also renamed.
        * cfgloop.h (duplicate_loop): Declare.
        * tree-flow.h (collect_defs, allocate_new_names, rename_op)
        (rename_variables_in_bb, free_new_names): Declare.

2004-05-20  Zdenek Dvorak  <>

	* tree-scalar-evolution.c (first_iteration_non_satisfying_noev_ev,
	first_iteration_non_satisfying_ev_ev): Check the assumptions returned
	by number_of_iterations_cond.

2004-05-13  Devang Patel  <>

	* cfgloop.c (get_loop_body_in_bfs_order): New.
	(flow_loop_exit_edges_find): Set EDGE_LOOP_EXIT.
	* cfgloop.h (get_loop_body_in_bfs_order): New.

2004-05-13  Zdenek Dvorak  <>

	* expr.c (expand_expr_real_1): Use REF_ORIGINAL information
	* tree-flow.h (force_gimple_operand, rewrite_address_base): Declare.
	* tree-ssa-loop-ivopts.c (force_gimple_operand): Expand.
	(add_address_candidates): Add candidates with constant offset
	(idx_remove_ssa_names, unshare_and_remove_ssa_names,
	rewrite_address_base): New.
	(rewrite_use_address): Use rewrite_address_base.
	* tree-into-ssa.c (register_new_def): Remove unused code.
	* tree-scalar-evolution.c (chrec_contains_symbols_defined_in_loop):
	Handle invariants correctly.
	* tree-cfg.c (tree_split_block): Do not modify the statements.
	* tree.h (REF_ORIGINAL): New macro.

2004-05-12  Sebastian Pop  <>

	* tree-chrec.c (chrec_evaluate): Use the type of the chrec
	instead of integer_type_node when folding operations.
	(chrec_apply): Factor chrec_type calls.
	(chrec_eval_next_init_cond): Removed.
	(chrec_convert): Don't propagate overflows introduced by convert.
	* tree-chrec.h (chrec_eval_next_init_cond): Removed.
	* tree-scalar-evolution.c (first_iteration_non_satisfying_noev_ev,
	first_iteration_non_satisfying_ev_ev): Use number_of_iterations_cond
	instead of computing the loop counts.

2004-05-10  Zdenek Dvorak  <>

	* loop-invariant.c (find_invariant_insn): Handle trapping insns

2004-05-10  Sebastian Pop  <>

	* tree-chrec.h (build_chrec_top_type): Disabled, return chrec_top.
	* tree-scalar-evolution.c (first_iteration_non_satisfying_noev_ev,
	first_iteration_non_satisfying_ev_noev): Use the type of the chrec
	instead of integer_type_node when folding operations.
	(number_of_iterations_to_overflow): New.
	(first_iteration_non_satisfying_ev_ev): Implement some cases.
	(set_nb_iterations_in_loop): Return chrec_top on overflow.
	(follow_ssa_edge_in_rhs): Handle type conversions "a = (type) rhs".
	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
	Convert the result of find_loop_niter_by_eval to the same type as niter
	before comparing.

2004-05-09  Zdenek Dvorak  <>

	* loop-iv.c (determine_max_iter, shorten_into_mode,
	iv_number_of_iterations): Handle constants correctly.
	* rtl.h (get_mode_bounds): Declaration changed.  Duplicate declaration
	* stor-layout.c (get_mode_bounds): Return a constant suitable for
	a target mode.

2004-05-06  Sebastian Pop  <>

	* tree-chrec.h (build_chrec_top_type): Check that the type has
	min and max values before taking their values.

2004-05-06  Sebastian Pop  <>

	* tree-chrec.h (build_chrec_top_type): New.
	* tree-chrec.c (chrec_fold_multiply_ival_cst,
	chrec_fold_multiply_ival_ival, chrec_fold_plus_1): Use
	build_chrec_top_type instead of returning chrec_top.

	* tree-data-ref.c (dump_data_dependence_relation): Don't dump
	direction per subscript.
	(analyze_array): Use an extra boolean parameter for the access
	mode: read or write.
	(analyze_array_top, finalize_ddr_dependent): New.
	(compute_direction_vector, set_all_subscripts_to): Removed.
	(initialize_data_dependence_relation): The dependence relation
	is unknown when one of the references base name is NULL_TREE.
	(subscript_dependence_tester, build_classic_dist_vector,
	build_classic_dir_vector, compute_affine_dependence):
	Use finalize_ddr_dependent.
	(build_classic_dir_vector): When one of the directions is
	dir_star, the subscript coupling cannot deduce independence.
	(compute_all_dependences): Renamed compute_rw_wr_ww_dependences.
	(compute_rw_wr_ww_dependences): Don't compute read-read
	relations.  Don't compute the reversed dependence relation.
	(find_data_references_in_loop): Use analyze_array_top when the
	MODIFY_EXPR contains a VUSE/VDEF that is not an ARRAY_REF.
	* tree-data-ref.h (data_reference): Add a field is_read.
	(DR_IS_READ): New.
	(analyze_array): Change declaration.
	* tree-vectorizer.c (vect_analyze_data_refs): Adapt the use of
	analyze_array to the new prototype.  Pass in the read or write

2004-04-30  Zdenek Dvorak  <>

	* tree-ssa-loop-niter.c: New file.
	* (tree-ssa-loop-niter.o): New.
	* cfgloop.h (struct loop): Add bounds field.
	* df.c (df_reg_clobber_gen): Removed.
	(df_bb_rd_local_compute, df_insn_refs_record, df_rd_local_compute):
	Make more effective for hard regs.
	* loop-invariant.c (check_maybe_invariant, find_defs,
	find_invariant_insn): Handle hard regs.
	* tree-chrec.c (chrec_fold_plus_poly_poly, chrec_fold_multiply,
	chrec_fold_multiply, chrec_merge): Handle types correctly.
	(chrec_convert): Use count_ev_in_wider_type.
	* tree-chrec.h (count_ev_in_wider_type): Declare.
	* tree-flow.h (struct tree_niter_desc): Moved from
	(number_of_iterations_cond, number_of_iterations_exit,
	loop_niter_by_eval, find_loop_niter_by_eval,
	estimate_numbers_of_iterations, can_count_iv_in_wider_type,
	free_numbers_of_iterations_estimates): Declare.
	* tree-scalar-evolution.c (count_ev_in_wider_type, scev_reset,
	simple_iv): New.
	(number_of_iterations_in_loop): Check that the exit condition
	is tested in every iteration.
	* tree-scalar-evolution.h (scev_reset, simple_iv): Declare.
	* tree-ssa-loop-ivcanon.c (MAX_ITERATIONS_TO_TRACK,
	chain_of_csts_start, get_base_for, get_val_for,
	loop_niter_by_eval, find_loop_niter_by_eval): Moved to
	* tree-ssa-loop-ivopts.c (struct tree_niter_desc): Moved to
	(force_gimple_operand): Accept a variable for the target of
	the assignment.
	(create_iv, rewrite_use_nonlinear_expr,
	rewrite_use_address, rewrite_use_compare,
	rewrite_use_outer): Changed due to this.
	(tree_ssa_iv_optimize_init): Call estimate_numbers_of_iterations.
	(get_var_def): Removed.
	(find_givs_in_stmt_scev): Use simple_iv.
	(inverse, number_of_iterations_cond): Moved to tree-ssa-loop-niter.c.
	(determine_number_of_iterations): Use number_of_iterations_exit.
	(idx_find_step, find_interesting_uses_address): Use
	(force_var_cost): Determine the costs more precisely.
	(tree_ssa_iv_optimize_finalize): Call
	(tree_ssa_iv_optimize_loop): Call scev_reset.
	* varasm.c (force_const_mem): Set MEM_NOTRAP_P flag.
	* config/rs6000/rs6000.c (rs6000_emit_move): Set MEM_NOTRAP_P flag.

2004-04-27  Sebastian Pop  <>

	* lambda-code.c (build_int_cst): Moved...
	* tree-data-ref.c (int_cst_value): Moved...
	* tree-ssa-loop-ivopts.c (int_cst_value, build_int_cst): Moved...
	* tree.c (int_cst_value, build_int_cst):
	* tree.h (int_cst_value, build_int_cst): Declare.

	* tree-chrec.h (is_chrec, symbolic_parameter_expr_p): Removed.

	* tree-chrec.c (evolution_function_is_affine_multivariat): Check that
	the left part is a polynomial before taking its variable.

	* tree-elim-check.c (prove_truth_value): Update the use of
	tree_is_* functions.
	* tree-fold-const.h (tree_is_ge, tree_is_gt, tree_is_le, tree_is_lt,
	tree_is_eq, tree_is_ne): Return true when decidable, and use a
	parameter for returning the result.

	* tree-scalar-evolution.c (types_forbid_solutions_p): Removed.
	first_iteration_non_satisfying_ev_noev): Update the use of
	tree_is_* functions.  Use no_evolution_in_loop_p instead of
	evolution_function_is_constant_p.  Extends the analyzer to
	symbolic loop counts.
	(first_iteration_non_satisfying): Factorize code.

2004-04-26  Zdenek Dvorak  <>

	* config/rs6000/ Fix merge problem.

2004-04-25  Zdenek Dvorak  <>

	Merge from tree-ssa branch (lno-merge-20040425).

2004-04-25  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (force_gimple_operand): Strip useless type
	(number_of_iterations_cond): Fix typo.
	(rewrite_use_address): Fix.

2004-04-23  Daniel Berlin  <>

	* tree-loop-linear.c (linear_transform_loops): Add invariants array.
	* lambda-code.c (gcc_tree_to_linear_expression): Change arguments
	to include invariants array, and an int, instead of a bool.
	Handle invariants.
	(invariant_in_loop): New function.
	(gcc_loop_to_lambda_loop): Add support for invariants as bounds,
	and NE_EXPR tests.
	(gcc_loopnest_to_lambda_loopnest): Add invariants argument,
	init the invariants array, and pass it along to gcc_loop_to_lambda_loop.
	(lle_to_gcc_expression): Handle invariants and simple linear offsets.
	(lambda_loopnest_to_gcc_loopnest): Ditto.
	Also use the right test if the step is negative.

2004-04-23  Zdenek Dvorak  <>

	* tree-scalar-evolution.c (instantiate_parameters_1): Handle changed
	semantics of analyze_scalar_evolution.  Split off from ...
	(instantiate_parameters): ... here.

2004-04-23  Zdenek Dvorak  <>

	* tree-scalar-evolution.c (analyze_scalar_evolution_1): Keep
	loop invariants in symbolic form.  Use
	compute_scalar_evolution_in_loop for expressions defined in subloops.
	(chrec_contains_symbols_defined_in_loop): Check for non-strict
	(compute_scalar_evolution_after_loop): Renamed back to
	(follow_ssa_edge_inner_loop_phi, interpret_loop_phi):
	Changed due to the renaming.
	(get_scalar_evolution): Return chrec_not_analyzed_yet for complicated
	(compute_scalar_evolution_in_loop): Compute the evolution of the
	expression returned by compute_overall_effect_of_inner_loop.

2004-04-22  Sebastian Pop  <>

	* tree-elim-check.c (prove_truth_value_gt, prove_truth_value_lt,
	prove_truth_value_le, prove_truth_value_ge, prove_truth_value_eq,
	prove_truth_value_ne): Resurrect.
	(prove_truth_value_symbolic): New.  Disabled for the moment.
	(prove_truth_value): Use it when this function fails on unknown.
	(try_eliminate_check): Factorize the code.
	* tree-scalar-evolution.c (compute_scalar_evolution_after_loop):
	Fix the description comment.

2004-04-21  Zdenek Dvorak  <>

	* tree-flow.h (linear_transform_loops): Prototype changed.
	* tree-vectorizer.h (vectorize_loops): Ditto.
	* tree-loop-linear.c (linear_transform_loops): Remove unused
	* tree-vectorizer.c (vectorize_loops): Ditto.
	* tree-scalar-evolution.c (scalar_evolution_info): Type changed
	to hash table.
	(new_scev_info_str): Use xmalloc instead of ggc_alloc.
	(hash_scev_info, eq_scev_info, del_scev_info,
	gather_stats_on_scev_database_1): New functions.
	(find_var_scev_info, dump_chrecs_stats, gather_stats_on_scev_database,
	scev_initialize, scev_finalize): Work with hash table instead of a
	(scev_elim_checks, scev_vectorize): Do not pass unused arguments to

2004-04-21  Sebastian Pop  <>

	* tree-chrec.c (chrec_apply): Fail on chrec_top when the chrec
	contains symbols defined in the inner loop.  Otherwise perform
	the computation with symbols.
	(no_evolution_in_loop_p): Same.  Moved from here...
	* tree-chrec.h (no_evolution_in_loop_p): ...there.  Define it inline.
	(chrec_contains_symbols_defined_in_loop): Declare.
	* tree-scalar-evolution.c (nb_set_scev, nb_get_scev): New counters.
	(set_scalar_evolution, get_scalar_evolution): Count the number of calls.
	(chrec_contains_symbols_defined_in_loop): Defined.
	(compute_scalar_evolution_after_loop, first_iteration_non_satisfying_1,
	analyze_scalar_evolution_in_loop): Initialize boolean values.
	(dump_chrecs_stats): Dump the get/set counters.

2004-04-21  Sebastian Pop  <>
            Zdenek Dvorak  <>

	* tree-scalar-evolution.c (compute_scalar_evolution_in_loop):
	Use superloop_at_depth.
	(analyze_scalar_evolution): Keep a symbolic form instead of

2004-04-21  Zdenek Dvorak  <>

	* tree-scalar-evolution.c (instantiate_parameters): Handle casts
	* tree-ssa-loop-manip.c (add_exit_phis_edge): Do not add unnecessary
	phi nodes.
	* tree-ssa-loop.c (tree_ssa_loop_opt): Do not call create_preheaders.

2004-04-20  Sebastian Pop  <>

	* tree-scalar-evolution.c (scev_info_str, new_scev_info_str,
	find_var_scev_info, set_scalar_evolution, get_scalar_evolution):
	Store a single scalar evolution per definition.
	(compute_overall_effect_of_inner_loop): Renamed
	(compute_scalar_evolution_in_loop): New.
	(analyze_scalar_evolution): Use the helper function.
	(analyze_scalar_evolution_1): Helper recursive function.
	Avoid multiple set/get in the scev database when recursively called.

2004-04-20  Dorit Naishlos <>

        * tree-vectorizer.c (vect_create_index_for_array_ref): Use create_iv
        instead of creating iv's from scratch.
        (vect_transform_loop_bound): Likewise.

2004-04-20  Sebastian Pop  <>

	* tree-chrec.c (chrec_fold_multiply_ival_cst,
	chrec_fold_multiply_ival_ival, chrec_fold_plus_1): When the fold
	resulted in an overflow, conservatively answer chrec_top.

2004-04-20  Sebastian Pop  <>

	* tree-chrec.c (chrec_fold_multiply_ival_cst): Compute the min
	and max on the multiplication result.
	(chrec_fold_negate): Removed.
	* tree-chrec.h (chrec_fold_negate): Removed.
	* tree-scalar-evolution.c (interpret_rhs_modify_expr):
	Use chrec_fold_minus instead of chrec_fold_negate.

2004-04-20  Sebastian Pop  <>

	* tree-chrec.h (evolution_function_is_constant_p): Be careful.
	* tree-data-ref.c (analyze_siv_subscript_affine_affine): Renamed
	analyze_subscript_affine_affine.  Exchange the CHREC_VARIABLEs for
	(analyze_miv_subscript): Use directly analyze_subscript_affine_affine,
	and avoid the call to evolution_function_is_constant_p.

2004-04-20  Sebastian Pop  <>

	* tree-chrec.c (chrec_apply): Fail on chrec_top for symbolic chrecs.
	(no_evolution_in_loop_p): Return false when non decidable, use
	a parameter for returning the result.
	* tree-chrec.h (no_evolution_in_loop_p): Modify its declaration.
	* tree-scalar-evolution.c (add_to_evolution, multiply_evolution):
	Avoid the use of no_evolution_in_loop_p.
	(add_to_evolution_1, multiply_evolution_1): New.
	(multiply_by_expr_the_loop_evolution, add_expr_to_loop_evolution,
	build_polynomial_evolution_in_loop): Removed.
	(first_iteration_non_satisfying_1, analyze_scalar_evolution_in_loop):
	Modify the use of no_evolution_in_loop_p.
	* tree-ssa-loop-ivopts.c (find_givs_in_stmt_scev,
	find_givs_in_stmt_scev): Check that the result of scev analysis
	does not contain symbols.

2004-04-19  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (idx_contains_abnormal_ssa_name_p,
	contains_abnormal_ssa_name_p): New functions.
	(find_bivs, find_bivs, find_givs_in_stmt_scev):
	Handle ssa names occuring in abnormal phis.
	* tree-ssa-loop-im.c (movement_possibility): Ditto.

2004-04-18  Dorit Naishlos <>

        * tree-vectorizer.c (create_index_for_array_ref): Remove code under
        #ifdef POINTER_ARITHMETIC.
        (vect_create_data_ref): Likewise. Support array addressing
        instead of pointer arithmetic in vectorized code.

2004-04-16  Zdenek Dvorak  <>

	Merge from tree-ssa branch:

	2004-03-25  Diego Novillo  <>
		* tree-ssa-alias.c (struct alias_info): Change type of field
		'num_references' to varray_type.  Update all users.

2004-04-15  Zdenek Dvorak  <>

	* tree-into-ssa.c (struct mark_def_sites_global_data): Change type of
	names_to_rename to sbitmap.
	(insert_phi_nodes_for, insert_phi_nodes_1, insert_phi_nodes):
	Allocate worklist globally.
	(ssa_mark_def_sites_initialize_block, ssa_mark_phi_uses,
	ssa_mark_def_sites, ssa_rewrite_initialize_block,
	ssa_rewrite_phi_arguments, ssa_rewrite_stmt, rewrite_ssa_into_ssa):
	Use sbitmaps instead of bitmaps.

2004-04-15  Sebastian Pop  <>

	* tree-scalar-evolution.c (instantiate_parameters): Don't keep
	symbols after instantiation.  Fully instantiate parameters,
	or fail on chrec_top.

2004-04-15  Sebastian Pop  <>

	* tree-fold-const.h (chrec_merge_types): Move it...
	* tree-chrec.c (multiply_int, divide_int, add_int, substract_int,
	integer_divides_p, lcm, gcd, update_initial_condition_to_origin,
	remove_initial_condition, ): Removed.
	(evolution_function_in_loop_num): Renamed into
	(hide_evolution_in_loop, hide_evolution_in_other_loops_than_loop): New.
	(chrec_merge_types): ... here.
	(chrec_merge): Answer chrec_top on EXPONENTIAL_CHREC.
	(ziv_subscript_p, siv_subscript_p, analyze_ziv_subscript,
	analyze_siv_subscript, analyze_siv_subscript_cst_affine,
	analyze_siv_subscript_affine_cst, analyze_siv_subscript_affine_affine,
	chrec_steps_divide_constant_p, analyze_miv_subscript,
	analyze_overlapping_iterations): Moved from here...
	* tree-chrec.h (evolution_function_in_loop_num): Rename declaration.
	(hide_evolution_in_other_loops_than_loop, hide_evolution_in_loop): New.
	(analyze_overlapping_iterations): No longer extern.

	* tree-data-ref.c (ziv_subscript_p, siv_subscript_p,
	analyze_siv_subscript, analyze_siv_subscript_cst_affine,
	analyze_siv_subscript_affine_cst, analyze_siv_subscript_affine_affine,
	chrec_steps_divide_constant_p, analyze_miv_subscript,
	analyze_overlapping_iterations): ... there.
	access_functions_are_affine_or_constant_p): Moved down.
	(compute_all_dependences): Moved down.  Now is static.
	(build_classic_dir_vector): New.
	(find_data_references): Renamed find_data_references_in_loop.
	Now is static.
	(compute_data_dependences_for_loop): New.
	(analyze_all_data_dependences): Use compute_data_dependences_for_loop.
	* tree-data-ref.h (dd_info_available): Don't declare it extern.

	* tree-scalar-evolution.c (dd_info_available): Declare static.
	(select_outer_and_current_evolutions): Removed.
	(stats_*): Move the static variables in the chrec_stats structure.
	(chrec_stats): New structure.
	(first_iteration_non_satisfying_1): In the multivariate case,
	don't forget that the outer loops can change the number of iterations.
	(cannot_analyze_loop_nb_iterations_yet): Removed.
	(follow_ssa_edge_inner_loop_phi): Refine the case where the
	evolution of the inner loop is symbolic.
	(number_of_iterations_in_loop): Factor the end of the cases.

	* tree-dg.c (classic_dist, classic_dir): Declared static.
	(dg_delete_graph): Delete the classic_dist and classic_dir.
	(dg_create_graph): Adapt to use compute_data_dependences_for_loop.
	(gate_ddg, gate_delete_ddg, pass_ddg, pass_delete_ddg): Moved in
	* tree-dg.h (dg_create_graph): Pass in struct loops.

2004-04-15  Dorit Naishlos <>

        * tree-data-ref.h (struct data_reference): New field "aux".
        * tree-vectorizer.h (aligned_access_p, unknown_alignment_for_access_p):
        New functions.
        (DR_MISLAIGNMENT): New macro, for accessing the new 'aux' field in
        * tree-vectorizer.c: (vect_analyze_data_refs_alignment): New function.
        (vect_compute_data_refs_alignment): New function.
        (vect_compute_data_ref_alignment): New function.
        (vect_enhance_data_refs_alignment): New function.
        (vect_force_dr_alignment_p): New function.
        (vect_align_data_ref): Use new functions aligned_access_p and
        (vect_analyze_data_ref_access): Alignment related checks moved to new
        functions that deal with alignment.
        (vect_analyze_data_refs): Likewise.
        (vect_analyze_loop): Call vect_analyze_data_refs_alignment.

2004-04-15  Zdenek Dvorak  <>

	* loop-invariant.c (may_assign_reg_p): Prevent unused parameter
	* tree-ssa-loop-manip.c (find_use_block, find_use_blocks,
	defined_inside_loop_p): Removed.
	(add_exit_phis_var, add_exit_phis, rewrite_into_loop_closed_ssa):
	Make more efficient.
	(find_uses_to_rename_use, find_uses_to_rename_stmt,
	find_uses_to_rename): New functions.

2004-04-15  Zdenek Dvorak  <>

	* tree-flow.h (compute_global_livein): Declare.
	* tree-into-ssa.c (struct def_blocks_d): New field
	(compute_global_livein): Export.
	(set_def_block): Record phi_blocks.
	(get_def_blocks_for): Allocate phi_blocks.
	(mark_def_sites): Changed due to set_def_block change.
	(ssa_mark_def_sites_initialize_block, ssa_mark_def_sites):
	Make virtual defs be kills.
	(insert_phi_nodes_for): Handle old phi nodes more efficiently.
	(def_blocks_free): XFREE the bitmaps.
	* tree-ssa-loop-manip.c (add_exit_phis_use, add_exit_phis_stmt):
	(get_loops_exits): Return bitmap.
	(add_exit_phis_var, find_use_block, find_use_blocks,
	defined_inside_loop_p): New functions.
	(add_exit_phis): Use add_exit_phis_var.
	(rewrite_into_loop_closed_ssa): Reorganize.
	* tree-ssa-loop.c (pass_loop): Add garbage collection.

2004-04-14  Zdenek Dvorak  <>

	* tree-chrec.c (chrec_convert): Handle extending correctly.
	* tree-scalar-evolution.c (set_scev_keep_symbolic): Removed.
	(set_scalar_evolution): Do not use it.
	(get_scalar_evolution): Only handle ssa names and constants.
	(interpret_loop_phi): When interpreting subloop, compute the
	evolution in outer loop afterwards.
	(analyze_scalar_evolution_in_loop): New.
	* tree-scalar-evolution.h (analyze_scalar_evolution_in_loop): Declare.
	* tree-ssa-loop-ivopts.c: Include tree-fold-const.h, tree-chrec.h
	and tree-scalar-evolution.h.
	(tree_ssa_iv_optimize_init): Call scev_initialize.
	(determine_biv_step, find_bivs, mark_bivs,
	find_givs_in_stmt): Use scev analyzer.
	(find_givs_in_stmt_scev): New function.
	(find_induction_variables): Remove TODO comment.
	(force_var_cost): Test for TREE_INVARIANT, not for
	(find_optimal_iv_set): Update comment.
	(tree_ssa_iv_optimize_finalize): Call scev_finalize.

2004-04-13  Zdenek Dvorak  <>

	* tree-ssa.c (raise_value): Removed.
	(get_eq_name, check_phi_redundancy): New.
	(kill_redundant_phi_nodes): Use standard algorithm.

2004-04-12  Zdenek Dvorak  <>

	* tree-ssa-loop-manip.c (allocate_new_names): Use duplicate_ssa_name.

2004-04-10  Daniel Berlin  <>

	* lambda-code.c (lambda_loopnest_transform): Add comments.

2004-04-09  David Edelsohn  <>

	Backport from mainline:
        * config/rs6000/t-linux64 (bispecs): Don't add -mlong-double-128 for
        32-bit builds when defaulting to 32-bit.

2004-04-09  Zdenek Dvorak  <>

	* loop-iv.c (iv_number_of_iterations): Sign extend the constant value
	appropriately for the target mode.
	* tree-fold-const.c (tree_fold_gcd): Make more efficient.
	* tree-ssa-loop-manip.c (add_exit_phis_use): Do not add unnecessary
	(rewrite_into_loop_closed_ssa): Fix comment.

2004-04-09  Zdenek Dvorak  <>

	* cfgrtl.c (purge_dead_edges): Clean the EDGE_ABNORMAL_CALL flags.
	* loop-iv.c (iv_number_of_iterations): Handle the case when we prove
	that the loop does not roll.
	* opts.c (decode_options): Enable -floop-optimize2 and
	-ftree-loop-optimize by default.
	* tree-cfg.c (factored_computed_goto_label,
	factored_computed_goto): Removed.
	(factor_computed_gotos): Do not record them.
	(disband_implicit_edges): Do not unfactor computed jumps.
	* tree-ssa-loop-ivopts.c (force_gimple_operand): Give correct types
	to temporary variables.
	(idx_force_simple, create_iv, rewrite_use_nonlinear_expr,
	rewrite_use_address, rewrite_use_compare, rewrite_use_outer):
	Changed due to force_gimple_operand change.
	(find_bivs): Handle ill-typed assignments correctly.

2004-04-04  Zdenek Dvorak  <>

	* passes.c (rest_of_compilation): Enable rest_of_handle_loop2 by
	* tree-scalar-evolution.c (scev_initialize): Find loop exits.

2004-04-02  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (rewrite_use_outer): Do not remove ssa names

2004-04-01 Mostafa Hagog  <>
	   Dorit Naishlos <>

        * config/rs6000/ ("*ctrsi_internal1", "*ctrsi_internal2",
        "*ctrdi_internal1", "*ctrdi_internal2", "*ctrsi_internal3",
        "*ctrsi_internal4", "*ctrdi_internal3", "*ctrdi_internal4",
        "*ctrsi_internal5", "*ctrsi_internal6", "*ctrdi_internal5",
        "*ctrdi_internal6"): Replace register_operand with nonimmediate_operand

2004-03-31  Zdenek Dvorak  <>

	* tree-into-ssa.c (ssa_rewrite_initialize_block): Update
	(ssa_rewrite_phi_arguments): Ditto.
	* tree-ssa.c (kill_redundant_phi_nodes): Prevent replacing
	ssa names that occur in abnormal phi nodes.
	* tree-ssa-loop-ivopts.c (get_var_def): Handle non-invariant
	non-ssa name operands.
	* java/decl.c (java_init_decl_processing): Initialize

2004-03-31  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (idx_find_step): Prevent misscompilation
	in case the index overflows.

2004-03-31  Zdenek Dvorak  <>,
	    Dorit Naishlos <>

	* tree-scalar-evolution.c (dump_chrecs_stats): Prevent format warning.

2004-03-30  Zdenek Dvorak  <>

	* lambda-code.c (gcc_loop_to_lambda_loop): Changed due to changes in
	* tree-data-ref.c (analyze_array_indexes, analyze_array): Ditto.
	* tree-elim-check.c (try_eliminate_check): Ditto.
	* tree-vectorizer.c (vect_analyze_scalar_cycles): Ditto.
	* tree-chrec.c (chrec_fold_plus_1): Handle exponential + peeled chrec
	correctly.  Use correct types.
	(chrec_fold_negate): New.
	(chrec_merge):  Short-circuit the case when the merged values are
	(no_evolution_in_loop_p): Handle chrec_top correctly.
	(chrec_convert): Handle polynomial and exponential chrecs corectly.
	(chrec_type): Use TREE_TYPE.
	* tree-chrec.h (chrec_fold_negate): Declare.
	* tree-phinodes.c (create_phi_node): Do not initialize PHI_MARKED.
	* tree-scalar-evolution.c: Handle evolutions analysed from different
	loops correctly.  Do not use PHI_MARKED.  Use correct types.
	* tree-scalar-evolution.h (analyze_scalar_evolution,
	instantiate_parameters): Declaration changed.
	(struct scev_info_str): Moved to tree-scalar-evolution.c.
	(new_scev_info_str): Moved to tree-scalar-evolution.c.
	* tree-ssa-loop-manip.c (add_exit_phis_use): Just add exit phis for
	superloops of the loop containing the definition.
	* tree.h (PHI_MARKED): Removed.
	(tree_phi_node): Field 'marked' removed.

2004-03-30  Sebastian Pop  <>

	* tree-chrec.c (chrec_contains_symbols): Factorize conditions,
	chrec_not_analyzed_yet is a NULL_TREE.
	* tree-chrec.h (prove_truth_value_{lt, le, ge, ne, gt, eq}.c):
	evolution_function_is_peeled_affine_p): New.
	* tree-data-ref.c (analyze_all_data_dependences): Dump some
	statistics on the data dependences.
	* tree-elim-check.c (not_code, prove_truth_value): New.
	(try_eliminate_check): Use prove_truth_value.
	* tree-fold-const.h (tree_is_ne): New.
	* tree-scalar-evolution.c (types_forbid_solutions_p,
	gather_stats_on_scev_database): New functions.
	(nb_iterations_less, nb_iterations_eq, nb_iterations_ne): Removed.
	(set_nb_iterations_in_loop): Be more careful on overflow.
	(number_of_iterations_in_loop): Use first_iteration_non_satisfying.
	* tree-scalar-evolution.h (first_iteration_non_satisfying,
	gather_stats_on_scev_database): Declared.

2004-03-30  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (iv_value): Use correct type.
	(may_eliminate_iv): Add a fixme comment.

2004-03-29  Devang Patel  <>

	* tree-flow.h (tree_ssa_loop_version): Add new parameter, basic_block *.
	(update_lv_condition): New.
	* tree-ssa-loop-manip.c (copy_phi_nodes): nreverse copied phi nodes list
	to ensure that phi nodes remain in same order.
	(lv_update_pending_stmts): Do not nreverse pending list.
	(lv_adjust_loop_header_phi): Walk two phi nodes list in parallel.
	(tree_ssa_loop_version): Now condition_bb is input parameter.
	(update_lv_condition): New.
	(test_loop_versioning): Use update_lv_condition.
	* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Update function
	tree_ssa_loop_version () call by adding 4th parameter.

2004-03-29  Richard Guenther <>

	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
	Fix unused vars warning with -disable-checking.
	* df.c (df_reg_def_chain_create, df_reg_use_chain_create): Ditto.

2004-03-27  Zdenek Dvorak  <>

	* cfghooks.c (split_edge): Update IRREDUCIBLE_LOOP flags.
	* tree-flow-inline.h (bsi_after_labels): New.
	* tree-flow.h (struct ssa_name_ann_d): Add need_phi_state field.
	(bsi_after_labels, rewrite_ssa_into_ssa, duplicate_ssa_name,
	tree_ssa_dce_no_cfg_changes, rewrite_into_loop_closed_ssa,
	verify_loop_closed_ssa, compute_phi_arg_on_exit): Declare.
	(tree_loop_optimizer_init): Declaration changed.
	* tree-into-ssa.c (struct mark_def_sites_global_data): Add
	names_to_rename and ssa_names fields.
	(insert_phi_nodes, get_value_for, set_value_for, set_def_block,
	set_livein_block, insert_phi_nodes_1, insert_phi_nodes_for,
	register_new_def, get_reaching_def, rewrite_into_ssa): Handle
	rewriting of ssa names.
	(get_phi_state, set_phi_state, ssa_mark_def_sites_initialize_block,
	ssa_mark_phi_uses, ssa_mark_def_sites, duplicate_ssa_name,
	ssa_rewrite_initialize_block, ssa_rewrite_phi_arguments,
	ssa_rewrite_finalize_block, ssa_rewrite_stmt, rewrite_ssa_into_ssa):
	New functions.
	* tree-scalar-evolution.c (scev_initialize): Changed due to
	tree_loop_optimizer_init change.
	* tree-ssa-dce.c (perform_tree_ssa_dce, perform_tree_ssa_dce,
	tree_ssa_cd_dce): Handle no cfg changes mode.
	(tree_ssa_dce_no_cfg_changes): Resurrect.
	* tree-ssa-loop-im.c (move_computations): Preserve loop closed ssa.
	* tree-ssa-loop-ivopts.c (struct version_info): Field outermost_usage
	(update_outermost_usage, find_outermost_usage): Removed.
	(ip_normal_pos): Fix.
	(tree_ssa_iv_optimize_init): Do not call find_outermost_usage.
	(find_interesting_uses_stmt): Use loop closed ssa form.
	(find_interesting_uses_outside): New.
	(find_interesting_uses): Use it.
	(determine_iv_cost): Prefer IP_NORMAL to IP_END.
	(split_loop_exit_edge, protect_loop_closed_ssa_form_use,
	protect_loop_closed_ssa_form, compute_phi_arg_on_exit): New functions.
	(rewrite_use_outer): Preserve loop closed ssa form.
	(tree_ssa_iv_optimize): Verify loop closed ssa form.
	* tree-ssa-loop-manip.c (mfb_redirect_exit_edges): Removed.
	(free_new_names): Free old ssa names.
	(extend_exit_phi_nodes, add_exit_phis_edge,
	add_exit_phis_use, add_exit_phis_stmt, add_exit_phis,
	get_loops_exits, rewrite_into_loop_closed_ssa,
	check_loop_closed_ssa_use, check_loop_closed_ssa_stmt,
	verify_loop_closed_ssa): New functions.
	(tree_duplicate_loop_to_header_edge): Use loop closed ssa form.
	(tree_ssa_loop_version): Handle irreducible loops correctly.
	* tree-ssa-loop.c (tree_loop_optimizer_init): Create loop closed ssa
	(tree_ssa_loop_opt, copy_loop_headers): Changed due to
	tree_loop_optimizer_init change.

2004-03-25  Sebastian Pop  <>

	* tree-data-ref.c (subscript_dependence_tester): Removed.
	(build_classic_dist_vector): Implement the subscript tester:
	test for different distances carried by the same loop.

2004-03-23  Sebastian Pop  <>

	* tree-cfg.c (print_loop): Modify dump formatting.
	(debug_loop_ir): Renamed tree_debug_loops.
	(tree_debug_loop): New.
	* tree-chrec.c: Restructure for handling more carefully types.
	* tree-chre.h: Same.
	* tree-fold-const.h: Same.
	* tree-fold-const.c: Same.
	* tree-scalar-evolution.c: Same.
	* tree-scalar-evolution.h: Same.
	* tree-data-ref.c (dump_data_dependence_relation): Remove the
	dump of the base_name because it produces too many conflicts in
	the diffs of the testsuite.
	(compute_all_dependences): Use pointers to the dependence_relations varray.
	(int_cst_value, build_classic_dist_vector): New.
	(find_data_references): Use pointers to datarefs varray.
	(analyze_all_data_dependences): Compute the classic distances.
	* tree-data-ref.h: Declare functions.
	* tree-dg.c (dg_create_graph): Update the uses of the data-ref functions.
	* tree-flow.h (debug_loop_ir): Renamed to tree_debug_loops.
	(tree_debug_loop): Declare.

2004-03-23  Zdenek Dvorak  <>

	* tree-flow.h (tree_ssa_dce_no_cfg_changes): Declaration removed.
	* tree-ssa-dce.c (remove_dead_stmt): Invalidate dominators if we
	thread the edge.
	(tree_ssa_dce_no_cfg_changes): Removed.
	(perform_tree_ssa_dce, tree_ssa_dce, perform_tree_ssa_dce): Remove
	no cfg changes mode.
	* tree-ssa-loop-ivopts.c (force_gimple_operand): Handle overflowed
	(find_interesting_uses_outer_or_nonlin): New.
	(find_interesting_uses_op, find_interesting_uses_outer): Use it.
	(find_interesting_uses_cond, idx_record_use,
	find_interesting_uses_stmt): Changed due to find_interesting_uses_op
	(create_new_iv, remove_statement, rewrite_use_nonlinear_expr,
	rewrite_use_outer, tree_ssa_iv_optimize): Handle direct removal of
	unused ivs.
	(remove_unused_ivs): New.
	(tree_ssa_iv_optimize_loop): Call it.

2004-03-23  Zdenek Dvorak  <>

	* (SCEV_H): New.
	(tree-ssa-loop-ivcanon.o, tree-ssa-loop-ivopts.o,
	tree-scalar-evolution.o, tree-data-ref.o, tree-dg.o,
	tree-elim-check.o, tree-vectorizer.o, tree-loop-linear.o,
	lambda-code.o): Use it.
	* tree-chrec.h (build_interval_chrec, build_polynomial_chrec,
	build_exponential_chrec, build_peeled_chrec): Give a type to the
	chrec node.
	* tree-scalar-evolution.c (follow_ssa_edge_in_rhs): Preserve correct
	(analyze_evolution_in_loop): Fix test for edges from inside the loop.
	(scev_initialize): New.
	(scev_init): Use it.
	(scev_finalize): New.
	(scev_done): Use it.
	* tree-flow-inline.h (loop_of_stmt): Handle initialization statements
	without crash.
	* tree-scalar-evolution.h (scev_initialize, scev_finalize): Declare.

2004-03-23  Dorit Naishlos  <>

        * tree-vectorizer.c: (vect_align_data_ref): Check for DECL_ALIGN
        instead of TYPE_ALIGN. Check for DECL_EXTERNAL.
        (vect_analyze_data_refs): Check for DECL_EXTERNAL.

        Add documentation for functions.

2004-03-22  Dale Johannesen  <>

	* (OBJS-common):  Remove duplicate loop-iv.o.

2004-03-22  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c: Avoid usage of global variables.

2004-03-21  Zdenek Dvorak  <>

	* tree-ssa-loop-unswitch.o: New file.
	* (tree-ssa-loop-unswitch.o): Add.
	(tree-ssa-loop-im.o): Add flags.h dependency.
	* flags.h (flag_unswitch_loops): Declaration moved from ...
	* toplev.h (flag_unswitch_loops): ... here.
	* tree-flow.h (tree_ssa_loop_version): Declaration changed.
	(tree_ssa_unswitch_loops, estimate_loop_size): Declare.
	* tree-ssa-loop-im.c: Include flags.h.
	(movement_possibility, stmt_cost, move_computations_stmt):
	Handle unswitchable conditions.
	* tree-ssa-loop-ivcanon.c (estimate_loop_size): Export.
	* tree-ssa-loop-ivopts.c (find_interesting_uses_cond): Handle
	if (0) and if (1).
	* tree-ssa-loop-manip.c (tree_ssa_loop_version): Return the newly
	created loop.
	* tree-ssa-loop.c (tree_ssa_loop_opt): Call tree_ssa_unswitch_loops.

2004-03-20  Zdenek Dvorak  <>

	Merge from tree-ssa branch (lno-merge-20040321).

2004-03-20  Dorit Naishlos <>

        * tree-vectorizer.c: (vect_init_vector): New function.
        (vect_get_vec_def_for_operand): Support loop invariant uses.
        (vect_is_simple_use): Likewise.
        (vect_mark_stmts_to_be_vectorized): Likewise.
        (vect_analyze_scalar_cycles): Redundant check removed.

        (vect_analyze_operations): Don't fail for vdefs that have uses
        outside the loop.

        (vect_stmt_relevant_p): A call to get_stmt_operands removed (already
        performed at new_loop_vec_info).
        (vect_mark_stmts_to_be_vectorized): Likewise.

        (need_imm_uses_for): New Function.
        (vectorize_loops): Add call to compute_immediate_uses and free_df.

2004-03-20  Zdenek Dvorak  <>

	* tree-chrec.c (chrec_fold_multiply_ival_cst): Handle negative
	constants correctly.
	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
	Enable use of scev.

2004-03-20  Zdenek Dvorak  <>

	PR optimization/14658
	* loop-invariant.c (move_invariant_reg): Handle assignments
	with nontrivial lhs correctly.

2004-03-18  Zdenek Dvorak  <>

	* df.c (df_reg_def_chain_create, df_reg_use_chain_create): Do not clean
	up the old information here.
	(df_reg_def_chain_clean, df_reg_use_chain_clean): New.
	(df_analyse_subcfg): Call them.

2003-03-18  Zdenek Dvorak  <>

	* tree-flow.h (loop_commit_inserts): Declare.
	* tree-ssa-loop-im.c (commit_inserts): Rename to...
	(loop_commit_inserts): ... this.
	* move_computations (move_computations, determine_lsm): Use
	* tree-ssa-loop-ivopts.c (AVG_LOOP_NITER): New macro.
	(struct iv): New field use_id.
	(struct version_info): New field preserve_biv.
	(alloc_iv, record_use, free_loop_data): Initialize new fields.
	(enum use_type): Add USE_OUTER.
	(dump_use, find_interesting_uses_op, add_derived_ivs_candidates,
	determine_use_iv_cost, rewrite_use): Handle USE_OUTER.
	(dump_cand, find_interesting_uses_stmt, add_candidate_1,
	determine_use_iv_cost_condition, determine_iv_cost, set_cost,
	create_new_iv, rewrite_use_nonlinear_expr): Handle final value
	(find_interesting_uses_outer, add_iv_outer_candidates,
	may_replace_final_value, determine_use_iv_cost_outer,
	remove_statement, rewrite_use_outer): New functions.
	(var_at_use): Replaced by ...
	(var_at_stmt): ... this.
	(get_computation_at): Split from ...
	(get_computation): ... here.
	(get_computation_cost_at): Split from ...
	(get_computation_cost): ... here.
	(iv_value): Split from ...
	(cand_value_at): ... here.
	(may_eliminate_iv, rewrite_use_compare): Reflect these changes.
	(tree_ssa_iv_optimize_loop): Call loop_commit_inserts.
	* tree-ssanames.c (make_ssa_name): Handle NULL argument.

2003-03-18  Devang Patel  <>

	* tree-ssa-live.c (new_tree_live_info): Set num_blocks to
	last_basic_block instead of n_basic_blocks.
	(calculate_live_on_entry): Use last_basic_block instead of
	(calculate_live_on_exit): Same.

2004-03-17  Zdenek Dvorak  <>

	* tree-cfg.c (thread_jumps): Don't thread jumps over loop headers.
	* tree-flow.h (rewrite_into_ssa): Declaration changed.
	(kill_redundant_phi_nodes, tree_loop_optimizer_init): Declare.
	* tree-optimize.c (execute_todo): Do not free vars_to_rename.
	(execute_one_pass): Do not allocate vars_to_rename.
	(tree_rest_of_compilation): Allocate vars_to_rename.
	* tree-scalar-evolution.c (number_of_iterations_in_loop): Handle
	loops exited when condition is true.
	(initialize_scalar_evolutions_analyzer): Use tree_loop_optimizer_init.
	* tree-ssa-chrec.c (how_far_to_positive): Handle chrec_top correctly.
	* tree-ssa-dom.c (tree_ssa_dominator_optimize): Changed due to
	rewrite_into_ssa change.
	* tree-ssa-loop-im.c (move_computations, determine_lsm): Ditto.
	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
	Use scev analyser.
	* tree-ssa-loop-manip.c (allocate_new_names): Update name memory
	* tree-ssa-loop.c (tree_loop_optimizer_init): New.
	(tree_ssa_loop_opt, copy_loop_headers): Use it.
	* tree-ssa.c (rewrite_into_ssa): Use argument to decide whether
	to rename all variables.
	(rewrite_all_into_ssa): New.
	(pass_build_ssa): Use it.
	(kill_redundant_phi_nodes): Export.

2004-03-15  Andrew Pinski  <>

	* tree-ssa-return.c (tree_ssa_return):
	Move check for NULL return value above check
	for a modify expr.

2004-03-13  Zdenek Dvorak  <>

	* tree-scalar-evolution.c (gate_scev_iv_canon): Do not check rtl
	level flags here.
	* tree-ssa-loop-ivcanon.c (get_base_for): Verfify that the argument
	of the phi node is a constant.
	(loop_niter_by_eval, create_canonical_iv, try_unroll_loop_completely,
	canonicalize_loop_induction_variables): Handle loops with more than
	one exit.
	(find_loop_niter_by_eval): New.
	(canonicalize_induction_variables): Check rtl level flags here.

2004-03-12  Andrew Pinski  <>

	* tree-ssa-return.c (tree_ssa_return):
	Only do it when we have a modify expr.

	* tree-ssa-return.c (tree_ssa_return):
	Add new comments and fix some old ones.

2004-03-12  Falk Hueffner  <>

	* tree-pass.h: Declare pass_return.

2004-03-11  Andrew Pinski  <>

	PR optimization/14135
	* tree-ssa-return.c: New file.
	* (tree-ssa-return.o): Add.
	* tree-optimize.c (init_tree_optimization_passes): Add
	* timevar.def (TV_TREE_RETURN): New.

2004-03-12  Zdenek Dvorak  <>

	* tree-ssa-loop-ivcanon.o: New file.
	* (tree-ssa-loop-ivcanon.o): Add.
	* flags.h (flag_unroll_loops): Declare.
	* loop-invariant.c (record_use): Fix.
	* params.def (PARAM_MAX_COMPLETELY_PEELED_INSNS): Increment.
	* timevar.def (TV_TREE_LOOP_IVCANON): New.
	* toplev.h (flag_unroll_loops): Declaration moved to flags.h.
	* tree-flow.h (enum tree_ann_type): Remove MISC_ANN.
	(struct tree_ann_common_d): Add aux field.
	(struct misc_ann_d): Removed.
	(struct stmt_ann_d): Removed aux field.
	(union tree_ann_d): Removed misc field.
	(canonicalize_induction_variables): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add
	* tree-pass.h (pass_scev_iv_canon): Declare.
	* tree-scalar-evolution.c (scev_iv_canon, gate_scev_iv_canon,
	pass_scev_iv_canon): New.
	(scev_done): Run cfg cleanup.
	* tree-ssa-loop-im.c (LIM_DATA, determine_invariantness_stmt,
	move_computations_stmt, schedule_sm): Use aux field in common
	part of annotations.
	* tree-ssa-loop-manip.c (allocate_new_names, rename_op,
	free_new_names): Use common aux field.
	(tree_duplicate_loop_to_header_edge): Fix memory leak.
	* tree-ssa.c (mark_def_sites): Fix.
	* tree-vectorizer.h (set_stmt_info, vinfo_for_stmt): Use aux field in
	common part of annotations.
	* gcc.dg/tree-ssa/ivcanon-1.c: New test.

2004-03-11  Zdenek Dvorak  <>

	* (lambda-mat.o, lambda-trans.o, lambda-code.o): Add TM_H

2004-03-09  Olga Golovonevsky <>
            Dorit Naishlos <>

        * tree-vectorizer.c: (vect_transform_binop): Removed.
        (vect_transform_op): New function instead of vect_transform_binop,
        to support both unary and binary operations.
        (vect_is_supportable_binop): Removed.
        (vect_is_supportable_op): New function instead of
        vect_is_supportable_binop to support additional codes.
        * tree-vectorizer.h: (operation_type): New enum type declared.
        * config/rs6000/ (andvv16qi3, andv8hi3, one_cmplv16qi2,
        one_cmplv8hi2, one_cmplv4si2, iorv16qi3, iorv8hi3,): New modelling.
        (*movv4si_internal): Relax condition.
        (*movv8hi_internal1): Likewise.
        (*movv16qi_internal1): Likewise.
        (*movv4sf_internal1): Likewise.

2004-03-09  Zdenek Dvorak  <>

	* (df.o): Remove FIBHEAP_H dependency.
	(invariant.o): Add df.h dependency.
	* df.c: Do not include fibheap.h.
	(df_bb_table_realloc, df_analyse_subcfg, free_reg_ref_chain,
	prune_to_subcfg, df_bb_modify, df_find_def, dataflow_set_a_op_b,
	dataflow_set_copy): New functions.
	(df_bitmaps_alloc, df_reg_def_chain_create, df_reg_use_chain_create,
	df_refs_update, df_reg_table_realloc, df_ref_create,
	df_bb_reg_def_chain_create, df_bb_reg_use_chain_create,
	df_bb_rd_local_compute, df_bb_ru_local_compute, df_bb_lr_local_compute,
	df_analyse_1, df_insn_modify): Support analysing only a part of the cfg.
	(df_rd_transfer_function, df_ru_transfer_function,
	df_lr_transfer_function): Type of bitmaps changed to void *.
	(hybrid_search_bitmap, hybrid_search_sbitmap): Merge into ...
	(hybrid_search): ... new function.
	(iterative_dataflow_bitmap, iterative_dataflow_sbitmap): Merge into ...
	(iterative_dataflow): ... new function. Avoid use of fibheaps for
	a worklist.  Do not process basic blocks unnecessarily.
	* df.h (struct ref): Add data field.
	(DF_REF_DATA): New macro.
	(df_analyse_subcfg, df_find_def): Declare.
	(transfer_function_sbitmap, transfer_function_bitmap): Replaced by ...
	(transfer_function): ... declare.
	(iterative_dataflow_sbitmap, iterative_dataflow_bitmap): Replaced by ...
	(iterative_dataflow): ... declare.
	(enum set_representation, struct dataflow): New.
	* loop-invariant.c: Include df.h.
	(struct loop_data): Remove modified_regs field.
	(struct def): Remove redundant fields.
	(struct use): Add insn field.
	(defs, adef, last_def, m_reg_info, reg_info): Removed.
	(struct reg): Removed.
	(record_def, note_insn_stores, find_defs_insn, find_defs_bb,
	get_current_def, record_dependencies_fer, record_dependencies,
	move_actual_defs): Removed.
	(find_defs, find_invariants_insn, create_new_invariant,
	find_invariants_bb, find_invariants_body, find_invariants,
	find_invariants_to_move, move_invariant_reg,
	move_invariants, move_single_loop_invariants,
	move_loop_invariants): Use df.c.
	(init_inv_motion_data): Do not initialize removed structures.
	(free_inv_motion_data, free_loop_data): Do not cleanup removed
	(check_dependencies, find_invariant_insn, record_uses): New.
	(record_use): Record the insn.
	(get_inv_cost): Update comments.

2004-03-09  Andreas Jaeger  <>

	* common.opt: Put tree-loop-linear at right place.

2004-03-09  Daniel Berlin  <>

	* Add lambda-mat.o, lambda-code.o, and tree-loop-linear.o.
	* common.opt: Add -ftree-loop-linear.
	* flags.h: Add flag_tree_loop_linear.
	* opts.c: Handle tree-loop-linear option.
	* timevar.def (TV_TREE_LINEAR_TRANSFORM): New.
	* tree-flow.h (linear_transform_loops): New prototype.
	* tree-optimize.c (pass_scev_linear_transform): New.
	* tree-pass.h (pass_scev_linear_transform): Ditto.
	* tree-scalar-evolution.c (scev_linear_transform): Ditto.
	(gate_scev): Add check for flag_tree_loop_linear.
	(gate_scev_linear_transform): New.
	* lambda-code.c: New file.
	* lambda-mat.c: New file.
	* lambda-trans.c: New file.
	* lambda.h: New file.
	* tree-loop-linear.c: New file.

2004-03-09  Andrew Pinski  <>

	* tree-ssa-phiopt.c (conditional_replacement):
	Initialize new_var to NULL to prevent the
	uninitialized warning.

	* tree-ssa-phiopt.c (conditional_replacement):
	Disable the making a new variable for different

	* tree-ssa-phiopt.c (conditional_replacement):
	Disable the use of non-gimple of invert_truthvalue.

2004-03-08  Andrew Pinski  <>

	* tree-ssa-phiopt.c (make_temp): New function.
	(tree_ssa_phiopt): Use absolute_replacement
	and value_replacement.
	(conditional_replacement): Handle the case
	the conditional is not a variable and
	the types do not match.
	Handle the case where invert_truthvalue
	would create non-gimple.
	(absolute_replacement): New function.
	(value_replacement): New function.

2004-03-08  Sebastian Pop  <>

	* tree-scalar-evolution.c (set_scalar_evolution,
	set_scalar_evolution_outer_value): Compute the loop number
	instead of passing it as a parameter.

2004-03-04  Zdenek Dvorak  <>

	* tree-ssa-loop-live.c (coalesce_tpa_members): Update the root
	variable of the partition.

2004-03-03  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (enum iv_position): Add IP_ORIGINAL.
	(struct iv_cand): Add incremented_at.
	(dump_cand, add_candidate_1, add_candidate, add_old_iv_candidates,
	var_at_use, get_computation, get_computation_cost,
	cand_value_at, determine_iv_cost, find_best_candidate,
	create_new_iv): Handle IP_ORIGINAL.
	(stmt_after_ip_original_pos, stmt_after_increment): New functions.
	(find_givs_in_stmt): Cast the values to the result type.
	(record_invariant): Do not record virtual operands.

2004-03-03  Daniel Berlin  <>

	* tree-scalar-evolution.c: Use pointers to varray instead of
	varrays for functions that insert in the scev database.

2004-03-03  Sebastian Pop  <>

	* (OBJS-common): Add tree-elim-check.o.
	(tree-chrec.o): Add dependence on tree-pass.h.
	(tree-elim-check.o): New rule.
	* tree-elim-check.c: New file.
	* basic-block.h (edge_source, edge_destination): New inlined
	* cfgloop.h (loop_nb_iterations): Added a comment on the use
	of this accessor.
	* common.opt (ftree-elim-checks): New flag.
	* flags.h (flag_tree_elim_checks): Declared here.
	* opts.c (decode_options): Set flag_tree_elim_checks to zero.
	(common_handle_option): Add case OPT_ftree_elim_checks.
	* timevar.def (TV_TREE_ELIM_CHECKS): Defined.
	* toplev.c (flag_tree_elim_checks): Defined.
	* tree-cfg.c (print_pred_bbs, print_succ_bbs, print_loop):
	Modify the dumping style.  Print nb_iterations.
	* tree-chrec.c, tree-chrec.h, tree-scalar-evolution.c,
	tree-scalar-evolution.h, tree-data-ref.c: New version of the
	scalar evolution algorithm.  Don't use a schedule for
	analyzing the scalar variables.
	* tree-fold-const.c (tree_fold_bezout): Define.
	* tree-fold-const.h (tree_fold_int_round_div,
	tree_fold_int_trunc_mod, tree_fold_int_ceil_mod,
	tree_fold_int_floor_mod, tree_fold_int_round_mod): Removed, because
	not used for the moment.
	(chrec_merge_types): New function.
	* tree-optimize.c (pass_scev_elim_checks): Register the pass.
	* tree-pass.h (pass_scev_elim_checks): Declare the pass.
	* tree-pretty-print.c (dump_generic_node): Print
	* tree-vectorizer.c: Modify the use of
	evolution loop in a third leaf instead of in TREE_TYPE.
	TREE_TYPE is then used in storing the type of the chrec.
	(PERIODIC_CHREC): Removed since it is not used for the moment.
	(PEELED_CHREC): New node.
	* doc/invoke.texi (fdump-tree-scev, fdump-tree-ddall): Correct
	the name of these flags.
	(ftree-elim-checks, fdump-tree-elck): Document.

2004-03-02  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (number_of_iterations_cond, cand_value_at):
	Cast the constants.

2004-03-01  Zdenek Dvorak  <>

	* (tree-ssa-loop-ivopts.o): Add HASHTAB_H dependency.
	* tree-ssa-loop-ivopts.c: Include hashtab.h.
	(old_highest_ssa_version): Rename to version_info_size.
	(struct tree_niter_desc): Split from ...
	(struct loop_data): ... here.
	(relevant): New variable.
	(tree_ssa_iv_optimize_init, set_iv, find_induction_variables,
	record_invariant, find_interesting_uses, add_old_ivs_candidates,
	determine_set_costs, free_loop_data, tree_ssa_iv_optimize_finalize):
	Use bitmap of relevant ssa names.
	(var_at_use): New function.
	(get_computation): Use it.
	(multiply_by_cost): Cache all results.
	(mbc_entry_hash, mbc_entry_eq): New functions.
	(number_of_iterations_cond): Split from ...
	(determine_number_of_iterations): ... here.
	(cand_value_at, may_eliminate_iv): New functions.
	(determine_use_iv_cost_condition, rewrite_use_compare): Implement iv

2004-03-01  Devang Patel  <>

	* tree-dg.c (dg_delete_graph): Reset varrays.
	(gate_ddg) : Check current loops.

2004-02-27  Zdenek Dvorak  <>

	* tree-cfg.c (cleanup_control_expr_graph): Prevent probability from
	* loop-invariant.c (get_current_def): Fix.
	* tree-ssa-loop-im.c (move_computations): Only call rewrite_into_ssa
	if vars_to_rename is nonempty.
	* tree-ssa-loop-ivopts.c (outermost_usage, ivs): Removed.
	(struct version_info): New.
	(version_info, max_inv_id): New variables.
	(struct cost_pair): Added depends_on field.
	(struct iv_use): Removed fields choices, n_choices, min_cost and
	(enum iv_position, dump_cand, ip_end_pos, add_candidate_1,
	determine_iv_cost, create_new_iv): IP_START position disabled.
	(find_optimal_iv_set_1, min_remaining_cost, undo_changes,
	execute_removal, add_forbidden_ivs, try_candidate): Removed.
	(dump_use): Do not dump removed fields.
	(ver_info, name_info, update_outermost_usage, record_invariant,
	find_invariants_stmt, find_depends, try_improve_iv_set): New functions.
	(find_outermost_usage): Handle uses in phis.
	(divide): Update comment.
	(tree_ssa_iv_optimize_init): Initialize version_info instead of ivs
	and outermost_usage.
	(set_iv, get_iv, find_induction_variables, add_old_ivs_candidates):
	Use version_info instead of ivs.
	(record_use): Do not initialize removed fields.
	(find_interesting_uses_op): Call record_use.
	(find_interesting_uses_stmt): Call find_invariants_stmt.
	(find_interesting_uses): Scan just the current loop.
	(set_use_iv_cost): Initialize depends_on field.
	(get_use_iv_cost): Return depends_on field.
	(get_computation): Handle special cases.
	(force_var_cost, split_address_cost, ptr_difference_cost,
	difference_cost, get_computation_cost, determine_use_iv_cost_generic,
	determine_use_iv_cost_address, determine_use_iv_cost_condition):
	Determine depends_on bitmap.
	(determine_use_iv_costs): Dump depends_on bitmap.
	(init_set_costs): Use information about invariants.
	(find_best_candidate, set_cost, get_initial_solution,
	find_optimal_iv_set): Take depends_on into account.
	(rewrite_uses): Use use->selected to select candidate.
	(free_loop_data, tree_ssa_iv_optimize_finalize): Cleanup version_info
	instead of ivs.  Free depends_on bitmaps.
	(tree_ssa_iv_optimize_loop): Do not pass iv_set to rewrite_uses.

2004-02-27  Zdenek Dvorak  <>

	* cfgloopmanip.c (loopify): Fix comment.
	* loop-iv.c (lowpart_byte, lowpart_subreg_p): Removed.
	(lowpart_subreg, simple_reg_p, iv_get_reaching_def, get_biv_step_1,
	iv_analyse_op, iv_analyse, get_iv_value): Use standard subreg
	manipulation functions.
	(simplify_using_assignment): Handle hardregs correctly.
	(canon_condition): Use swap_commutative_operands_p.
	(iv_number_of_iterations): Avoid overflow.
	* loop-unroll.c (unroll_loop_runtime_iterations): Pass additional
	argument to compare_and_jump_seq.
	* loop-unswitch.c (unswitch_loop, may_unswitch_on,
	unswitch_single_loop, compare_and_jump_seq): Handle comparisons of
	ccmode registers.
	* rtl.h (compare_and_jump_seq): Declaration changed.

2004-02-25  Dorit Naishlos <>

        * tree-vectorizer.h (assignment_vec_info_type): New enum value for
        * tree-vectorizer.c (vect_transform_assignment): New function.
        Support vectorization of assignment stmts.
        (vect_transform_stmt): Call vect_transform_assignment.
        (vect_is_supportable_assignment): New function.
        (vect_analyze_operations): Call vect_is_supportable_assignment.

        (vect_create_index_for_array_ref): Replace unsigned_intSI_type_node
        with size_type_node.
        (vect_transform_loop_bound): Likewise.

        (get_vectype_for_scalar_type): Avoid division by 0.

        (vect_analyze_operations): Apply check for no-out-of-loop-uses also
        to stmts that are marked irrelevant.

2004-02-25  Zdenek Dvorak  <>

	* tree-flow.h (for_each_index): Declare.
	* tree-ssa-loop-im.c (struct lim_aux_data): Add always_executed_in
	and sm_done fields.
	(struct use): New.
	(max_uid): New static variable.
	(outermost_invariant_loop, commit_inserts, may_move_till,
	force_move_till, record_use, free_uses, single_reachable_address,
	rewrite_uses, schedule_sm, determine_lsm_reg,
	loop_suitable_for_sm, determine_lsm_loop, determine_lsm): New functions.
	(add_dependency): Use outermost_invariant_loop.
	(set_level): Add sanity checking.
	(determine_invariantness_stmt): Set always_executed_in field.
	(move_computations_stmt): Modified.
	(move_computations): Use commit_inserts.
	(fill_always_executed_in): Take possibility of an infinite loop into
	(tree_ssa_lim): Call determine_lsm.
	* tree-ssa-loop-ivopts.c (for_each_index): Export.
	(rewrite_use_address): Improve handling of memory tags.

	* tree-ssa-loop.c (do_while_loop_p): Readd.
	(copy_loop_headers): Readd check for do_while_loop_p.
	* tree-ssa-operands.c (add_stmt_operand): Modified.

2004-02-21  Zdenek Dvorak  <>

	Merge from tree-ssa branch (lno-merge-20040221).

2004-02-20  Devang Patel  <>

	* tree-vectorizer.c (vect_analyze_data_ref_dependence): Use
        ddg_direction_between_stmts ().

2004-02-20  Devang Patel  <>

	* tree-data-ref.h (data_dependence_direction): Add new member
        * tree-dg.h (tree-data-ref.h): Include.
        (ddg_direction_between_stmts, ddg_distance_between_stmts): New decls.
        * tree-dg.c (find_ddr_between_stmts, ddg_direction_between_stmts,
        ddg_distance_between_stmts): New functions.

2004-02-19  Devang Patel  <>

	* tree-dg.c (dg_delete_edges, dg_delete_node, dg_delete_graph,
	dg_delete_edge, gate_delete_ddg): New functions.
	(pass_delete_ddg): New.
	* tree-dg.h (dg_delete_graph, dg_delete_edge): New extern decls.
	* tree-optimize.c (init_tree_optimization_passes): Add new pass
	* tree-pass.h (pass_delete_ddg): New extern.

2004-02-19  Zdenek Dvorak  <>

	* tree-flow.h (create_iv): Declare.
	* tree-ssa-loop-ivopts.c (create_iv): New function.
	(create_new_iv): Use create_iv.

2004-02-19  Zdenek Dvorak  <>

	* tree-ssa-loop.c (do_while_loop_p): New function.
	(copy_loop_headers): Do not peel do-while loops.

2004-02-19  Zdenek Dvorak  <>

	* loop-invariant.c: New file.
	* (loop-invariant.o): New.
	* cfgloop.h (init_set_costs, global_cost_for_size,
	move_loop_invariants): Declare.
	* toplev.c (rest_of_handle_loop2): Call move_loop_invariants.
	(lang_dependent_init): Call init_set_costs.
	* tree-ssa-loop-ivopts.c (avail_regs, res_regs, small_cost, pres_cost,
	spill_cost): Made static.
	(global_cost_for_size): Export.
	(ivopts_global_cost_for_size, init_set_costs): New functions.
	(determine_set_costs): Do not initialize set cost constants.
	Use ivopts_global_cost_for_size.
	(try_candidate, find_optimal_iv_set_1, set_cost): Use

	* cfgloop.c (fill_sons_in_loop): Fix typo in comment.

2004-02-17  Devang Patel  <>

	* tree-vectorize.c (vect_create_data_ref): Set TREE_ADDRESSABLE bit.
	(vectorize_loops): Reset loop->aux.

2004-02-16  Devang Patel  <>

        * (TREE_FLOW_H): Add tree-dg.h
        (OBJS-common): Add tree-dg.o
        (gtype-desc.o): Depend on tree-dg.h
        (tree-dg.o): New rule.
        (GTFILES): Add tree-data-ref.h, tree-data-ref.h
        * common.opt (ftree-ddg): Add new option.
        * flags.h (flag_ddg): New extern.
        * gengtype.c (open_base_files): Add tree-dg.h and tree-data-ref.h in
        the list.
        * opts.c (decode_option): Set flag_ddg to zero.
        (common_handle_option): Handle OPT_ftree_ddg.
        * timevar.def (TV_DEP_GRAPH): New.
        * toplev.c (flag_ddg): New flag.
        (lang_independent_options): Add entry for -ftree-ddg.
        * tree-data-ref.c (compute_all_dependences): Make externally visible.
        * tree-data-ref.h (data_reference, subscript, data_dependence_relation)
        Add GTY markers.
        (compute_all_dependences): Make externally visible.
        * tree-dg.c: New file.
        * tree-dg.h: New file.
        * tree-flow-inline.h (dg_node_for_stmt): New function.
        * tree-flow.h (tree-dg.h): Include.
        (stmt_ann_d): New member, dg_node.
        * tree-optimize.c (init_tree_optimization_passes): Add pass_ddg.
        * tree-pass.h (PROP_scev): Define.
        (tree_opt_pass pass_ddg): Extern decl.
        * tree-scalar-evolution.c (pass_scev_anal): Provide PROP_scev property.
        * varray.c (element[NUM_VARRAY_DATA]): Add new member for dependence
        * varray.h (varray_data_enum): New member VARRAY_DATA_DG.
        (varray_data_tag): New member dg.
        (VARRAY_DG_INIT): New #define.
        (VARRAY_DG): New #define.
        (VARRAY_PUSH_DG): New #define.

2004-02-12  Zdenek Dvorak  <>

	* tree-optimize.c (init_tree_optimization_passes): Move ch after
	the first dominator optimization pass.
	* tree-ssa-loop.c (should_duplicate_loop_header_p,
	copy_loop_headers): Work over ssa.
	(pass_ch): Require and update ssa form.
	(mark_defs_for_rewrite, duplicate_blocks): New.

2004-02-10  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (for_each_index, prepare_decl_rtl,
	peel_address): Handle RESULT_DECL.

2004-02-10  Zdenek Dvorak  <>

	* loop-doloop.c (doloop_optimize): Use get_simple_loop_desc.
	* loop-init.c (loop_optimizer_finalize): Free the simple loop
	* loop-unroll.c (unroll_and_peel_loops): Do not free the simple loop
	(decide_peel_once_rolling, decide_peel_completely,
	decide_unroll_stupid): Test assumptions.
	decide_unroll_constant_iterations, decide_unroll_runtime_iterations,
	decide_peel_simple, peel_loop_simple, unroll_loop_stupid): Update
	number of iterations info.
	(unroll_loop_constant_iterations, unroll_loop_runtime_iterations,
	(loop_exit_at_end_p): Use get_simple_loop_desc.

2004-02-08  Zdenek Dvorak  <>

	* cfgloop.h (struct niter_desc): Add first_special, extend,
	extend_mode, delta and mult fields.
	(get_iv_value): Declare.
	* expr.c (force_operand): Handle subregs of expressions.
	* loop-doloop.c (doloop_valid_p): Test desc->infinite properly.
	* loop-iv.c (dump_iv_info): Dump new fields.
	(lowpart_byte, lowpart_subreg_p, lowpart_subreg,
	iv_constant, iv_subreg, iv_extend, iv_neg, iv_add, iv_mult,
	get_biv_step_1, get_biv_step, shorten_into_mode,
	canonicalize_iv_subregs): New functions.
	(simple_reg_p, simple_set_p, iv_get_reaching_def, iv_analyse_biv,
	iv_analyse_op, iv_analyse, iv_number_of_iterations): Handle subregs.
	* loop-unswitch.c (may_unswitch_on): Handle subregs.

2004-02-04  Zdenek Dvorak  <>

	* (tree-ssa-loop-ivopts.o): Add RECOG_H and insn-config.h
	* loop-iv.c (iv_analysis_loop_init): Ensure we only care about
	increments that are done just once each iteration.
	* timevar.def (TV_TREE_LOOP_IVOPTS, TV_TREE_CH): New.
	* tree-ssa-loop-ivopts.c: Include insn-config.h and recog.h.
	(INFTY): Increase.
	(struct iv_use): Add choices, n_choices, min_cost_cand and selected
	fields.  Rename field best_cost to min_cost.
	(dump_use): Dump new fields.
	(dump_uses, cst_and_fits_in_hwi, int_cst_value, build_int_cst,
	divide, strip_offset, add_cost, multiply_by_cost, get_address_cost,
	force_var_cost, peel_address, ptr_difference_const,
	split_address_cost, ptr_difference_cost, difference_cost,
	get_computation_cost): New functions.
	(find_induction_variables): Formating changes.
	(record_use): Initialize new fields.
	(add_old_ivs_candidates): Do not add invariants.
	(set_use_iv_cost): Set min_cost.
	(get_use_iv_cost): Fix.
	(get_computation): Use less memory.
	(determine_use_iv_cost_generic, determine_use_iv_cost_address,
	determine_use_iv_cost_condition, determine_iv_cost): Use
	new cost estimation functions.
	(compute_iv_set_cost): Removed.
	(struct undo_record): New.
	(use_with_min_choices, min_remaining_cost, undo_changes,
	execute_removal, add_forbidden_ivs, try_candidate, set_cost,
	get_initial_solution): New functions.
	(find_optimal_iv_set_1, find_optimal_iv_set): Made more effective.
	(create_new_ivs, rewrite_use_nonlinear_expr, rewrite_use_address):
	Unshare created expressions.
	(free_loop_data): Free new structures.
	(tree_ssa_iv_optimize_loop): Remove garbage collection.
	(tree_ssa_iv_optimize): Use TV_TREE_LOOP_IVOPTS timevar.
	* tree-ssa-loop.c (pass_ch): Use TV_TREE_CH timevar.

2004-02-02  Steven Bosscher  <>

	* common.opt: Re-order some options in ASCII collating order.

2004-01-30  Devang Patel  <>

	* cfgloopmanip.c (loopify): Always redirect switch_bb's BRANCH_EDGE,
	however redirect FALLTHRU_EDGE only if asked.
	* tree-ssa-loop-manip.c (tree_ssa_loop_version): Update FALLTHRU_EDGE
	pending stmts.

2004-01-29  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (find_optimal_iv_set_1, compute_iv_set_cost):
	Fix memory leak, speed up.
	(tree_ssa_iv_optimize_finalize): Move reseting of DECL_RTL...
	(free_loop_data): ... here.

2004-01-29  Zdenek Dvorak  <>

	* basic-block.h (FOR_BB_INSNS, FOR_BB_INSNS_REVERSE): New macros.
	* cfgloop.c (num_loop_branches): New function.
	* cfgloop.h (struct loop_desc): Add field strange.
	(struct loop): Remove fields simple, desc, has_desc.
	(num_loop_branches, get_simple_loop_desc, free_simple_loop_desc):
	(simple_loop_desc): New inline function.
	* cfgloopanal.c (count_loop_iterations): Set field strange.
	(simple_loop_exit_p): Initialize postincr properly.
	* loop-iv.c (assign_luids, mark_sets, simplify_using_initial_values):
	(iv_number_of_iterations): Restrict the number of iterations to the
	actual mode.
	(find_simple_exit): Check results with the old simple loop analyser.
	(get_simple_loop_desc, free_simple_loop_desc): New functions.
	* loop-unroll.c (loop_exit_at_end_p): New function.
	(unroll_and_peel_loops, peel_loops_completely,
	decide_unrolling_and_peeling, decide_peel_once_rolling,
	decide_peel_completely, peel_loop_completely,
	decide_unroll_constant_iterations, unroll_loop_constant_iterations,
	decide_unroll_runtime_iterations, unroll_loop_runtime_iterations,
	decide_peel_simple, decide_unroll_stupid): Use new iv analysis.
	* predict.c (predict_loops): Use new iv analysis.

	* tree-ssa-loop.c (copy_loop_headers): Predict entry edge from
	copied loop header to be taken.

	* tree-cfg.c (tree_find_edge_insert_loc,
	bsi_insert_on_edge_immediate): Return the newly created block.
	(bsi_commit_edge_inserts_1): Add parameter to
	tree_find_edge_insert_loc call.
	* tree-flow.h (bsi_insert_on_edge_immediate): Declaration changed.
	* tree-ssa-loop-ivopts.c (create_new_iv): Update loop for newly
	created block.

	* cfg.c (unlink_block): Clean prev_bb and next_bb fields.

2004-01-29  Devang Patel  <>

	* cfglayout.h (loopify): Add new bool parameter.
	* cfgloopmanip.c (loopify): Support new bool argument.
	* loop-unswitch.c (unswitch_loop): Supply additional argument 'true'
	to loopify.
	* tree-cfg.c (tree_block_label): Make externally visible.
	* tree-flow.h (tree_block_label, test_loop_versioning, tree_ssa_loop_version): New
	extern decls.
	* tree-ssa-loop-manip.c (lv_adjust_loop_entry_edge, lv_udate_pending_stmts,
	lv_adjust_loop_header_phi, tree_ssa_loop_version): New functions.
	* tree-ssa-loop.c (tree_ssa_loop_opt): Test loop versioning.

2004-01-29  Zdenek Dvorak  <>

	* tree-scalar-evolution.c (scev_analyze_inner_loop_phi): Add ;.

2004-01-29  Sebastian Pop  <>

	* (tree-ssa-dom.o): Depends on cfgloop.h.
	* tree-flow-inline.h (loop_of_stmt): New function.
	* tree-ssa-dom.c: Include cfgloop.h.
	(tree_ssa_dominator_optimize): Detect and finalize the natural
	loops structure.
	(simplify_rhs_and_lookup_avail_expr): Verify that the folded
	operations belong to the same loop.

	* cfgloop.h (loop): Rewrite comments for the nb_iterations field.
	* tree-data-ref.c (analyze_all_data_dependences): Increase the size
	of the dependence graph when computing all the dependences.
	* tree-optimize.c (init_tree_optimization_passes): Move the
	pass_scev after the pass_pre.
	* tree-scalar-evolution.h: Update comments.
	* tree-scalar-evolution.c (symbolically_analyze,
	scev_follow_ssa_edge_same_loop, scev_follow_ssa_edge_inner_loop,
	loop_is_strictly_included_in, scev_analyze_inner_loop_phi,
	draw_tree_cfg): New functions.
	(compute_value_on_exit_of_loop): Removed.
	(analyze_evolution): Mark phi nodes instead of looking into
	the already_visited array.
	(analyze_evolution_in_loop): Use scev_follow_ssa_edge_same_loop,
	(scev_analyze_modify_expr): Refine the wrap-around case.
	(scev_follow_ssa_edge): Handle edges to the current and inner loops
	separately calling scev_follow_ssa_edge_same_loop or
	(merge_branches_of_condition_phi_node): Restructure.
	(set_nb_iterations_in_loop): Add one to the number of iterations.
	When the loop copy headers is on, we always exit the loop after
	having executed once its body.
	(record_dependences_for_opnd): Do not record dependences on variables
	that are not in the current loop.
	(pass_scev_depend): Rename the pass from alldd to ddall.
	* tree-ssa-loop.c (gate_ch): New function.
	(pass_ch): Use gate_ch.
	* doc/invoke.texi (-ftree-ch, -fdump-tree-ch): Document flags.
	(fdump-tree-scev, fdump-tree-ddall): Update names, and comments.

	* common.opt (ftree-ch): Document.
	* flags.h (flag_tree_ch): Declare.
	* opts.c (flag_tree_ch): Set it on by default.
	(flag_scalar_evolutions, flag_all_data_deps): Turn off by default.
	(OPT_ftree_ch): Handle this case.
	* toplev.c (lang_independent_options): Register flag_tree_ch.

2004-01-28  Zdenek Dvorak  <>

	* cfghooks.c (split_block): Update probabilities.

	* cfgloopmanip.c (loopify): Always redirect branch edge to the new
	* loop-iv.c (canon_condition, simplify_using_condition): Export.
	(check_simple_exit): Do not allow cc mode registers.
	* loop-unroll.c (unroll_loop_runtime_iterations): Use
	* loop-unswitch.c (may_unswitch_on_p): Renamed to may_unswitch_on,
	returns the condition, use iv_analyse.
	(compare_and_jump_seq): New function.
	(unswitch_loops): Call iv_analysis_done.
	(unswitch_single_loop, unswitch_loop): Handle nontrivial invariants.
	* rtl.h (compare_and_jump_seq, canon_condition,
	simplify_using_condition): Declare.

2004-01-28  Zdenek Dvorak  <>

	* loop-iv.c: New.
	* loop-doloop.c: New.
	* (loop-doloop.o, loop-iv.o): Add.
	* alias.c (init_alias_analysis): Test flag_unroll_loops instead of
	* cfgloop.h (struct rtx_iv, struct niter_desc): New.
	(get_loop_level, iv_analysis_loop_init, iv_get_reaching_def,
	iv_analyse, find_simple_exit, iv_number_of_iterations,
	iv_analysis_done, doloop_optimize_loops): Declare.
	* cfgloopanal.c (get_loop_level): New.
	* common.opt (floop-optimize2): New.
	(fold-unroll-loops, fold-unroll-all-loops): Remove.
	* doloop.c (doloop_condition_get): Export.
	* flags.h (flag_old_unroll_loops, flag_old_unroll_all_loops):
	Declaration removed.
	* loop-unswitch.c (reversed_condition): Export.
	* loop.c (loop_invariant_p): Use flag_unroll_loops instead
	of flag_old_unroll_loops.
	* opts.c (common_handle_option): Handle -floop-optimize2,
	do not handle -fold-unroll-loops and -fold-unroll-all-loops.
	* params.def (PARAM_MAX_DOLOOP_INSNS): New.
	* rtl.h (get_mode_bounds, doloop_condition_get,
	reversed_condition): Declare.
	* stor-layout.c (get_mode_bounds): New function.
	* toplev.c (flag_old_unroll_loops, flag_old_unroll_all_loops):
	(flag_loop_optimize2): New.
	(rest_of_handle_loop_optimize): Use flag_unroll_loops instead
	of flag_old_unroll_loops.
	(rest_of_handle_loop2): Call doloop_optimize_loops.
	(rest_of_compilation): Use flag_loop_optimize2.
	(process_options): Remove flag_old_unroll_loops handling, add
	flag_loop_optimize2 handling.
	* toplev.h (flag_loop_optimize2): Declare.
	* unroll.c (unroll_loop): Use flag_unroll_all_loops instead of

2004-01-26  Dorit Naishlos <>

	* (tree-vectorizer.o): Remove dependency on real.h.
	* tree-vectorizer.c: (real.h): Remove included file.
        (vect_get_vec_def_for_operand): No need to explicitly use build_int_2
        and build_real.

        (vect_transform_loop_bound): Create loop IV update at loop exit
        block, following changes in loop control.

        (vectorize_loops): Remove debug printout.

        * config/rs6000/ (*movv4si_internal): More complex
        (*movv8hi_internal1): Likewise.
        (*movv16qi_internal1): Likewise.
        (*movv4sf_internal1): Likewise.

2004-01-25  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c (determine_set_costs): Do not use

2004-01-25  Zdenek Dvorak  <>

	* tree-ssa-loop-ivopts.c: New file.
	* (tree-ssa-loop-ivopts.o): Add.
	* expr.c (expand_expr_1): Handle expand_expr_1.
	* fold-const.c (invert_tree_comparison, invert_tree_comparison):
	* tree-cfg.c (stmt_bsi): New function.
	* tree-flow.h (stmt_bsi, tree_ssa_dce_no_cfg_changes,
	tree_ssa_iv_optimize): Declare.
	* tree-simple.c (get_base_symbol): Handle INDIRECT_REF.
	* tree-ssa-dce.c (tree_ssa_dce_no_cfg_changes): Split from ...
	(tree_ssa_dce): ... here.
	* tree-ssa-loop.c (tree_ssa_loop_opt): Call tree_ssa_iv_optimize.
	* tree-ssanames.c (make_ssa_name): Allow creating ssa name without
	* tree.h (invert_tree_comparison, swap_tree_comparison): Declare.

2004-01-25  Zdenek Dvorak  <>

	* doloop.c (doloop_optimize): Test for loop->top instead of

2004-01-22  Zdenek Dvorak  <>

	* tree-alias-common.c (HAVE_BANSHEE): Do not define it.
	(create_alias_vars): Do not test HAVE_BANSHEE value.

2004-01-22  Zdenek Dvorak  <>

	* tree-ssa-loop-manip.c: New file.
	* (tree-ssa-loop-manip.o): Add.
	* basic-block.h (struct reorder_block_def): New field copy_number.
	* cfghooks.c (split_block, make_forwarder_block): Update irreducible
	loop information.
	* cfgloopmanip.c (duplicate_loop_to_header_edge): Set copy_number.
	* tree-cfg.c (tree_duplicate_bb): Duplicate also virtual operands.
	* tree-flow.h (enum tree_ann_type): Add MISC_ANN.
	(struct misc_ann_d): New.
	(union tree_ann_d): Add misc field.
	(test_unrolling_and_peeling, tree_duplicate_loop_to_header_edge):
	* tree-ssa-loop.c (tree_ssa_loop_opt): Call
	* tree-ssa-operands.c (copy_virtual_operands): New.
	* tree-ssa-operands.h (copy_virtual_operands): Declare.

	* dominance.c: Fix comment.

	* cfgloopanal.c (mark_irreducible_loops): Rewriten.
	(struct edge, struct vertex, struct graph): New.
	(dump_graph, new_graph, add_edge, dfs, check_irred, for_each_edge,
	free_graph): New functions.

2004-01-21  Sebastian Pop  <>

	* tree-scalar-evolution.c (pass_scev): Don't use a name.
	(pass_scev_anal): Named this pass "scev".

2004-01-21  Dorit Naishlos <>

	* (tree-vectorizer.o): Add dependency on real.h.
        * tree-vectorizer.c: (vect_is_simple_use): Allow constants.
        (real.h): Included to support constants vectorization.
        (vect_get_vec_def_for_operand): New function.
        (vect_transform_binop): Use above new function.
        (vect_transform_store): Likewise.
        (vect_transform_load): Likewise.

        (vect_get_new_vect_var): Allow more flexibility in naming scheme.
        (vect_create_index_for_array_ref): Call vect_get_new_vect_var with a
        name prefix instead of a variable.
        (vect_create_data_ref): Likewise.
        (vect_create_destination_var): Likewise.

        (vect_analyze_data_refs): Temporarily restrict vectorizable data refs
	to ARRYA_RES which base is a VAR_DECL.
        (vect_create_data_ref): Support only VAR_DECL array base. Mark all
        vops for renaming.

        (vect_get_array_first_index): New function.
        (vect_create_index_for_array_ref): Consider array_first_index.
        (vect_analyze_data_ref_access): Likewise.

        (vect_get_loop_niters): Use number_of_iterations_in_loop.
        (vect_analyze_loop_form): Don't attempt to vectorize if
        number_of_iterations == 0.

        (vect_analyze_operations): Fix vectype analysis.

        (vect_create_index_for_array_ref): Fix code insertion in loop prolog.
        (vect_transform_loop_bound): Likewise.

2004-01-21  Zdenek Dvorak  <>,
	    Devang Patel <>

	* basic-block.h (struct reorder_block_def): Moved from cfglayout.h.
	(alloc_rbi_pool, initialize_bb_rbi, free_rbi_pool): Declare.
	* bb-reorder.c (copy_bb, copy_bb_p): Use duplicate_block hooks.
	* loop-unswitch.c (unswitch_loop): Ditto.
	* tracer.c (tail_duplicate): Ditto.
	* tree-ssa-loop.c (copy_loop_headers): Ditto.
	* cfg.c (rbi_pool): New.
	(alloc_rbi_pool, free_rbi_pool, initialize_bb_rbi): New functions.
	* cfghooks.c (can_duplicate_block_p, duplicate_block): New functions.
	* cfghooks.h (struct cfg_hooks): Add can_duplicate_block_p and
	duplicate_block hooks.
	(can_duplicate_block_p, duplicate_block): Declare.
	* cfglayout.c (cfg_layout_pool): Removed.
	(cfg_layout_initialize_rbi): Removed.
	(fixup_reorder_chain): Use initialize_bb_rbi.
	(cfg_layout_can_duplicate_bb_p, cfg_layout_duplicate_bb):
	Ir-independent parts moved to cfghooks.c.
	(cfg_layout_initialize): Use alloc_rbi_pool and initialize_bb_rbi.
	(cfg_layout_finalize): Use free_rbi_pool.
	(can_copy_bbs_p): Use can_duplicate_block_p.
	(copy_bbs): Use duplicate_block.
	* cfglayout.h (struct reorder_block_def): Moved to basic-block.h
	(cfg_layout_can_duplicate_bb_p, cfg_layout_duplicate_bb,
	cfg_layout_initialize_rbi): Declaration removed.
	* cfgrtl.c (cfg_layout_create_basic_block): Use initialize_bb_rbi.
	(cfg_layout_rtl_cfg_hooks): Add cfg_layout_can_duplicate_bb_p and
	* tree-cfg.c (build_tree_cfg): Call alloc_rbi_pool.
	(create_bb): Call initialize_bb_rbi.
	(delete_tree_cfg): Call free_rbi_pool.
	(tree_duplicate_bb): Ir independent parts moved to cfghooks.c.
	(tree_cfg_hooks): Add tree_can_duplicate_bb_p and tree_duplicate_bb.
	* tree-flow.h (tree_duplicate_bb): Declaration removed.

2004-01-21  Zdenek Dvorak  <>

	* tree-alias-common.c (create_alias_vars): Don't use
	andersen_alias_ops when we don't HAVE_BANSHEE.

	* tree-ssa-loop.c (pass_ch): Remove TODO_verify_ssa.

2004-01-20  Zdenek Dvorak  <>

	Merge from tree-ssa branch (lno-merge-20040120).

2004-01-18  Dorit Naishlos <>

        * tree-scalar-evolution.c: (get_loop_exit_condition): Exposed to
        external usage.
        * tree-scalar-evolution.h: (get_loop_exit_condition): Exposed to
        external usage.
        * tree-vectorizer.c: (vect_is_simple_iv_evolution): Additional argument
        to control how strict this function would be.
        (vect_create_index_for_array_ref): Invoke vect_is_simple_iv_evolution
        with "strict" set to true.
        (vect_transform_loop_bound): More general loop bound transformation
        scheme, independent of the loop exit condition form.
        (vect_analyze_scalar_cycles): Invoke vect_is_simple_iv_evolution with
        "strict" set to false.
        (vect_get_loop_niters): Use monev utilities/precomputed info -
        loop->nb_iterations and get_loop_exit_condition.

2004-01-17  Dorit Naishlos  <>

	* tree-vectorizer.c: (vect_get_name_for_new_var): Removed.
        (vect_get_new_vect_var): New function.  Replaces above function.
        (vect_create_index_for_array_ref): Call vect_get_new_vect_var
        instead of vect_get_name_for_new_var.
        (vect_create_data_ref): Likewise.
        (vect_create_destination_var): Likewise.
        * tree-vectorizer.h: (vect_var_kind): New enum type.

2004-01-15  Sebastian Pop  <>

	* tree-chrec.c (remove_initial_condition,
	add_expr_to_loop_evolution_1, add_expr_to_loop_evolution_2): New functions.
	(add_expr_to_loop_evolution): Use these functions.
	build_exponential_evolution_in_loop): Move from here...
	* tree-chrec.h (build_polynomial_evolution_in_loop,
	build_exponential_evolution_in_loop): Remove declarations.
	* tree-scalar-evolution.c (build_polynomial_evolution_in_loop,
	build_exponential_evolution_in_loop): ... to here.  Declare
	these functions static.
	(select_outer_and_current_evolutions): New function.
	(matched_an_increment, scev_analyze_modify_expr,
	analyze_scalar_evolution): Use this function.
	(add_to_evolution, multiply_evolution): Construct canonical
	chains of recurrences.

2004-01-14  Dorit Naishlos <>
            Sebastian Pop  <>

        * tree-vectorizer.c: (vect_is_simple_iv_evolution): Correctly use
        APIs of the new monev analyzer. Additional argument (loop_num).
        (vect_transform_loop_bound): Additional argument to
        (vect_analyze_scalar_cycles): Likewise.
        (vect_analyze_data_ref_access): Likewise.
        (vect_get_loop_niters): Likewise.

2004-01-14  Dorit Naishlos <>

        * tree-optimize.c: (optimize_function_tree): Cleanup.

        * tree-vectorizer.h: (DBG_VECT, DBG_VECT2): Removed.
        (vec_array_base_name_differ_p): Removed.
        (vec_analyze_array): Removed.
        (struct _stmt_vec_info): New field: loop.
        (STMT_VINFO_LOOP): New access function to above new field.
        (new_stmt_vec_info): Additional argument.

        * tree-vectorizer.c: (vect_is_simple_use): New function.
        (vect_is_supportable_binop): Added call to vect_is_simple_use().
        (vect_is_supportable_store): Added call to vect_is_simple_use().
        (vect_is_supportable_load): Added call to vect_is_simple_use().

        (vect_create_index_for_array_ref): Correct handling of accesses with
        an offset (e.g, a[i+OFF]).
        (vect_create_data_ref): Pass STMT as an argument to
        vect_create_index_for_array_ref, instead of an operand.
        (vect_transform_store): Handle accesses with an offset.
        (vect_transform_load): Handle accesses with an offset.

        (vect_create_data_ref): Set the mem_tag of the pointer used for the
        vector data-access to reflect correct may-alias info.

        (get_address_calculation_operands): Removed.
        (exist_non_indexing_operands_for_use_p): New function, in place of
        get_address_calculation_operands() to correctly handle induction (for
        now this means to detect and not attempt to vectorize computations
        like a[i]=i).
        (vect_analyze_scalar_cycles): call above new function instead of
        (vect_mark_stmts_to_be_vectorized): Likewise.

        (get_vectype_for_scalar_type): Added test of VECTOR_MODE_SUPPORTED_P.

        (new_stmt_vec_info): Takes also LOOP as an argument and initializes
        new field STMT_VINFO_LOOP.
        (new_loop_vec_info): Pass additional argument to new_stmt_vec_info.

        (vect_stmt_relevant_p): Use flow_bb_inside_loop_p instead of comparing
        (vect_analyze_operations): Likewise.

        (vect_align_data_ref): Removed stderr debug printouts, some of which
        replaced with code dumping dependending on TDF_DETAILS to dump_file.
        (vect_create_index_for_array_ref): Likewise.
        (vect_create_destination_var): Likewise.
        (vect_create_data_ref): Likewise.
        (vect_transform_binop): Likewise.
        (vect_transform_store): Likewise.
        (vect_transform_load): Likewise.
        (vect_transform_stmt): Likewise.
        (vect_transform_loop_bound): Likewise.
        (vect_transform_loop): Likewise.
        (vect_analyze_operations): Likewise.
        (vect_is_simple_iv_evolution): Likewise.
        (vect_analyze_scalar_cycles): Likewise.
        (vect_analyze_data_ref_dependences): Likewise.
        (vect_analyze_data_refs): Likewise.
        (vect_mark_relevant): Likewise.
        (vect_stmt_relevant_p): Likewise.
        (vect_mark_stmts_to_be_vectorized): Likewise.
        (vect_get_loop_niters): Likewise.
        (vectorize_loops): Likewise.

2004-01-13  Sebastian Pop  <>
            Daniel Berlin  <>

	* tree-fold-const.h (tree_fold_int_plus, tree_fold_int_minus,
	tree_fold_int_multiply): Remove NON_LVALUE_EXPR from the
	answers of the folder.  Fixes bootstraps for powerpc.

2004-01-12  Sebastian Pop  <>

	* tree-chrec.c (chrec_fold_plus, chrec_fold_multiply): Verify
	that there is no chrecs nested in the operands before calling
	the folder.
	(evolution_function_in_loop_num): When there is no evolution
	in the loop, return the initial condition.
	(evolution_part_in_loop_num): When there is no evolution
	in the loop, return NULL_TREE.
	(chrec_eval_next_init_cond): Adapt the function for the
	multivariate case.
	(tree_contains_chrecs): Avoid the use of double negation.
	* tree-chrec.h (chrec_eval_next_init_cond): Add a parameter
	for the dimension in which to evaluate the variation.
	* tree-scalar-evolution.c (is_ssa_name_a_version_of_variable,
	expression_contains_variable_p, remove_variable_from_expression,
	analyze_non_gimple_initial_condition, matched_an_increment,
	matched_an_exponentiation, matched_a_wrap_around,
	evolution_of_phi_already_analyzed_p): New static functions.
	(scev_analyze_modify_expr): Use these functions.  Refine the
	cases detected as wrap-around variables.
	(analyze_initial_condition): Don't erase the evolution in the
	previous dimensions when computing the initial condition for a
	new loop.
	(analyze_evolution_in_loop): Call the scev_analyze_modify_expr
	on the tree node, not on its evolution.
	(scev_follow_ssa_edge): In the case of an inner loop-phi-node,
	when the outer edge is a phi-node follow up the edge.
	(scev_follow_ssa_edge): Avoid the analysis of the inner loop
	when it has already been analyzed.
	(merge_evolutions): Refine the operation for zero, one, and
	more branches of evolutions.

2004-01-09  Sebastian Pop  <>

	* tree-scalar-evolution.c: New version of the analyzer.
	* tree-scalar-evolution.h: Same.
	* tree-chrec.c: Same.
	* tree-data-ref.c: Same.
	* tree-chrec.h: Same.
	* tree-data-ref.h: Same.
	* tree-fold-const.h: Same.

	* tree-vectorizer.c (vect_transform_loop_bound,
	vect_analyze_scalar_cycles, vect_analyze_data_ref_access,
	vect_analyze_data_refs, vect_get_loop_niters): Use the new
	interface of the analyzer.
	* tree-optimize.c (optimize_function_tree): Same.

2004-01-08  Zdenek Dvorak  <>

	* cfgloop.h (loop_is_included_in): Declaration removed.
	* tree-scalar-evolution.c (stmt_is_in_loop, stmt_is_not_in_loop,
	loop_is_included_in): Use existing functions to implement

2004-01-06  Sebastian Pop  <>

	* cfgloop.h (loop_is_included_in, outer_loop, inner_loop,
	next_loop, loop_num, loop_depth, loop_header,
	loop_nb_iterations, loop_num_exits, loop_exit_edges,
	loop_exit_edge): New inline functions.
	(loop_is_included_in): Declare here.
	* tree-flow-inline.h (loop_of_stmt): New inline function.
	* tree-scalar-evolution.c (loop_is_included_in): Remove declaration.
	(stmt_is_in_loop, stmt_is_not_in_loop): New functions.
	(loop_is_included_in, loop_is_included_in_rec): Moved up in the same file.

2004-01-06  Dorit Naishlos  <>

	* tree-vectorizer.c: Fix typos.

2004-01-05  Andreas Jaeger  <>

	* tree-vectorizer.h: Follow coding standards, remove extra
	* tree-vectorizer.c: Likewise.

	* tree-vectorizer.c (vectorize_loops): Output statistics to
	dump_file, fix printf string.
	(vect_transform_loop): Replace DBG_VECT code with code dumping
	dependend on TDF_DETAILS to dump_file.
	(vect_is_supportable_binop): Likewise.
	(vect_analyze_operations): Likewise.
	(get_address_calculation_operands): Likewise.
	(vect_analyze_scalar_cycles): Likewise.
	(vect_analyze_data_ref_dependence): Likewise.
	(vect_analyze_data_ref_access): Likewise.
	(vect_analyze_data_ref_accesses): Likewise.
	(vect_analyze_data_refs): Likewise.
	(vect_mark_relevant): Likewise.
	(vect_get_loop_niters): Likewise.
	(vect_mark_stmts_to_be_vectorized): Likewise.
	(vect_analyze_loop_form): Likewise.
	(vectorize_loops): Likewise.

	* tree-vectorizer.h (DBG_VEC): Remove.

2004-01-04  Zdenek Dvorak  <>

	* doloop.c (doloop_optimize): Update number of iterations for the
	loops entered at bottom.

2004-01-04  Andreas Jaeger  <>

	* common.opt: Re-order some options in ASCII collating orders.

2004-01-03  Zdenek Dvorak  <>

	* cfghooks.h (struct cfg_hooks): New fields split_block_after_labels
	and move_block_after, type of cfgh_make_forwarder_block field changed.
	(HEADER_BLOCK, LATCH_EDGE): Moved to cfgloop.c.
	(split_block_after_labels, move_block_after): New macros.
	(make_forwarder_block): Changed.
	* cfgloop.c (HEADER_BLOCK, LATCH_EDGE): Moved from cfghooks.h.
	(update_latch_info, mfb_keep_just, mfb_keep_nonlatch,
	fill_sons_in_loop): New functions.
	(canonicalize_loop_headers): Changed due to changes in
	* cfgloopmanip.c (split_loop_bb): Don't update dominators.
	(create_preheader): Use make_forwarder_block.
	(mfb_keep_just, mfb_update_loops): New.
	* cfgrtl.c (rtl_split_block_after_labels): New.
	(redirect_edge_with_latch_update): Removed.
	(rtl_make_forwarder_block): New sematics.
	(rtl_split_block): Update dominators.
	(rtl_cfg_hooks, cfg_layout_rtl_cfg_hooks):
	Add rtl_split_block_after_labels.
	* tree-cfg.c (tree_make_forwarder_block): Changed semantics.
	(create_blocks_annotations): Removed.
	(build_tree_cfg): Don't call create_blocks_annotations.
	(create_bb): Create annotations for a new block.
	(tree_split_edge): Don't call create_block_annotation.
	Update irreducible loop information.
	(tree_loop_optimizer_finalize): Add loop structure check.
	(tree_redirect_edge_and_branch_1): Return the original edge if
	no redirecting is neccessary.
	(tree_split_block): Make the semantics same as for rtl_split_block.
	(tree_split_block_after_labels, tree_move_block_after): New.
	(tree_cfg_hooks): Add tree_split_block_after_labels and

	* cfgloopanal.c (mark_irreducible_loops): Fix.
	* loop-unswitch.c (unswitch_loop): Fix.

	* (tree-ssa-loop.o): Add cfgloop.h and tree-inline.h
	* jump.c (next_nonnote_insn_in_loop, duplicate_loop_exit_test,
	copy_loop_headers): Removed.
	* rtl.h (copy_loop_headers): Declaration removed.
	* toplev.c (rest_of_compilation): Do not call loop header copying.
	* tree-dump.c (dump_files): Add .ch dump.
	* tree-flow.h (tree_duplicate_bb, copy_loop_headers): Declare.
	* tree-optimize.c (optimize_function_tree): Add loop header copying
	* tree-ssa-loop.c: Include cfgloop.h and tree-inline.h.
	(dump_file, dump_flags): Renamed to loop_dump_file and
	(call_expr_p, should_duplicate_loop_header_p, copy_loop_headers):
	* tree.h (enum tree_dump_index): Add ch dump.
	* doc/invoke.texi (-fdump-tree-copy-headers): Document.
	* testsuite/gcc.dg/tree-ssa/20030711-1.c: Update test outcome.
	* testsuite/gcc.dg/tree-ssa/20030714-2.c: Ditto.
	* testsuite/gcc.dg/tree-ssa/copy-headers.c: New test.
	* tree-cfg.c (tree_duplicate_bb): New function.

	* tree-ssa-loop-im.c: New file.
	* (tree-ssa-loop-im.o): Add.
	* params.def (PARAM_LIM_EXPENSIVE): New parameter.
	* tree-dump.c (dump_files): Move .loop dump.
	* cfgloop.h (superloop_at_depth, get_loop_body_in_dom_order): Declare.
	(loop_dump_file, loop_dump_flags): Declare variables.
	* cfgloop.c (superloop_at_depth, get_loop_body_in_dom_order): New
	* tree-flow.h (struct stmt_ann_d): Add aux field.
	(bsi_commit_edge_inserts): Declaration changed.
	(tree_ssa_lim): Declare.
	* tree-mudflap.c (mf_xform_derefs_1): Use in_array_bounds_p.
	* tree-optimize.c (optimize_function_tree): Move loop optimization
	* tree-sra.c (scalarize_structures): Modified due to
	bsi_commit_edge_inserts change.
	* tree-ssa-loop.c (tree_ssa_loop_opt): Call tree_ssa_lim.
	* tree-ssa.c (rewrite_trees, rewrite_vars_out_of_ssa): Modified due to
	bsi_commit_edge_inserts change.
	* tree.c (in_array_bounds_p): New function.
	* tree.h (in_array_bounds_p): Declare.
	(enum tree_dump_index): Move loop dump.
	* tree-cfg.c (bsi_commit_edge_inserts): Don't take update_annotations

	* tree-ssa.c (rewrite_into_ssa, rewrite_out_of_ssa): Ensure that the
	closed files are not used.

	* tree-tailcall.c (find_tail_calls, eliminate_tail_call): Update
	phi nodes for vdefs of the eliminated call.

2004-01-03  Sebastian Pop  <>

	* tree-optimize.c (optimize_function_tree): Move the closing brace of
	DCE2 to the right place.

2004-01-03  Sebastian Pop  <>

	* tree-vectorizer.c (vect_analyze_operations): Test vectorization_factor
	before computing modulo.

2004-01-02  Sebastian Pop  <>

	* tree-vectorizer.c (vect_is_supportable_binop): Returns false instead
	of NULL.

2004-01-02  Richard Henderson  <>

	* config/i386/i386.h (UNITS_PER_SIMD_WORD): New.

2004-01-02  Sebastian Pop  <>

	* tree-data-ref.c (vec_analyze_array, vec_array_base_name_differ_p,
	array_base_name_differ_p): Removed for fixing the previous patch.

2004-01-02  Richard Henderson  <>

	* target.h (struct gcc_target): Remove vectype_for_scalar_type.
	* target-def.h (TARGET_VECTYPE_FOR_SCALAR_TYPE): Remove.
	* config/rs6000/rs6000.c (rs6000_vectype_for_scalar_type): Remove.

	* tree.c (build_vector_type_with_mode): Rename from make_vector,
	remove unsignedp argument, update callers.
	(build_vector_type): New.
	* tree.h (build_vector_type): Declare it.
	* tree-vectorizer.c (get_vectype_for_scalar_type): Use it.

2004-01-02  Richard Henderson  <>

	* tree-scalar-evolution.c (finalize_scalar_evolutions_analyzer):
	Clear dump_file.

2004-01-02  Sebastian Pop  <>

	* tree-data-ref.c (vec_analyze_array): Renamed to analyze_array.
	(analyze_array): Removed.
	(find_data_references): Adapted to use the new analyze_array
	(array_base_name_differ_p): Moved to tree-data-ref.h.
	(vec_array_base_name_differ_p): Removed.
	* tree-data-ref.h (array_base_name_differ_p): Moved here.
	* tree-vectorizer.c (vect_analyze_data_ref_dependence): Use
	array_base_name_differ_p instead of vec_array_base_name_differ_p.
	(vect_analyze_data_refs): Use analyze_array instead of
	(vectorize_loops): Remove the initializers and finalizers of the
	scalar evolution analyzer.

2004-01-01  Dorit Naishlos <>

        * tree-vectorizer.c: New file. Implements loop vectorization
        * tree-vectorizer.h: New file.
        * (tree-vectorizer.c,tree-vectorizer.h): New files.
        * tree-dump.c: (dump_files): New dump file for the new
        vectorization pass.
        * tree.h: (TDI_vect): New dump index for the new vectorization
        * timevar.def (TV_TREE_VECTORIZATION): Support new
        vectorization pass.
        * opts.c: (flag_tree_vetorize): New flag to enable/disable the
        new vectorization pass.
        * flags.h: Same.
        * toplev.c: Same.
        * common.opt: (ftree-vectorize): Same.
        * doc/invoke.texi: Document above new options.
        * tree-optimize.c: (optimize_function_tree): Invoke the new
        vetorization pass.
        * tree-flow.h: (struct stmt_ann_d): New field (aux) to allow
        recording information per stmt.
        * tree-data-ref.c (vec_analyze_array): New function, exposing
        API to the vectorizer.
        (vec_array_base_name_differ_p): New function, exposing API to
        the vectorizer.
        * tree-data-ref.h: Same.
        * defaults.h: (UNITS_PER_SIMD_WORD): Define.
        * config/rs6000/rs6000.h: (UNITS_PER_SIMD_WORD): Same.
        * target-def.h (TARGET_VECTYPE_FOR_SCALAR_TYPE): Declare a new
        target hook for vectorization.
        * target.h (vectype_for_scalar_type): Same.
        * config/rs6000/rs6000.c: (rs6000_vectype_for_scalar_type):
        Implement the above new target hook.

2003-12-31  Sebastian Pop  <>

	* version.c (version_string): Change the identifier for the

2003-12-31  Sebastian Pop  <>
            Daniel Berlin  <>

	* tree-phinodes.c (create_phi_node): Initialise PHI_MARKED to 0.
	* tree-scalar-evolution.c (already_visited,
	node_already_visited_by_ssa_path): Removed.
	(analyze_evolution): Remove initialisation of already_visited.
	(construct_schedule): idem.
	(monev_follow_ssa_edge): use PHI_MARKED for deciding whether
	to analyze the phi-node.
	(follow_ssa_edge_and_record_dependences_rec): idem.
	* tree.h (PHI_MARKED): New macro.
	(tree_phi_node): Add a field marked.

2003-12-27  Sebastian Pop  <>

	* (OBJS-common): Added tree-chrec.o
	tree-scalar-evolution.o, tree-data-ref.o, tree-fold-const.o.
	(tree-optimize.o): Add dependencies on tree-fold-const.h
	tree-chrec.h tree-scalar-evolution.h tree-data-ref.h
	(tree-chrec.o, tree-scalar-evolution.o, tree-data-ref.o,
	tree-fold-const.o): New rules.
	* cfgloop.h (loop): New field nb_iterations.
	(loop_from_num): New function.
	* common.opt (fscalar-evolutions, fall-data-deps): Added.
	* flags.h (flag_scalar_evolutions, flag_all_data_deps): Declared.
	* opts.c (decode_options, common_handle_option): Initialize
        flag_scalar_evolutions and flag_all_data_deps.
	* toplev.c (flag_scalar_evolutions, flag_all_data_deps): Defined.
	(lang_independent_options): Add flag_scalar_evolutions and
	* tree-dump.c (scev, alldd): New extensions.
	* tree.h (tree_dump_index): Added TDI_scev and TDI_alldd.
	* tree-optimize.c (tree-fold-const.h, tree-chrec.h,
	tree-scalar-evolution.h, tree-data-ref.h): Included.
	(optimize_function_tree): Added the entry point for the analysis of
	scalar evolutions and data dependences.
	* tree-pretty-print.c (tree-fold-const.h, tree-chrec.h): Included.
	(dump_generic_node): Added code for dumping POLYNOMIAL_CHREC,
	PERIODIC_CHREC): New tree nodes.
	* varray.h (index_in_varray_tree, tree_is_in_varray_tree_p,
	index_in_varray_int, int_is_in_varray_int_p): New inlined functions.
	* tree-chrec.c, tree-chrec.h, tree-data-ref.c, tree-data-ref.h,
	tree-fold-const.c, tree-fold-const.h, tree-scalar-evolution.c,
	tree-scalar-evolution.h: New files.
	* doc/invoke.texi (-fdump-scalar-evolutions, -fdump-all-data-deps):
	* testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-[01..50].c : New testcases.
	* testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-[01..50].c.scev: Expected
	outputs for the scalar evolution analyzer.
	* testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-{10, 30, 31, 32, 33, 34,
	35, 36}.c.alldd: Expected outputs for the data dependence analyzer.
	* testsuite/gcc.dg/tree-ssa-chrec/tree-ssa-scev.exp: New file.
	* testsuite/lib/scantree.exp (diff-tree-dumps): New procedure.
	* ChangeLog.lno: New file.