contrib/gcc/tree-ssa-loop-ivopts.c

69 #include "tree.h"
76 #include "tree-flow.h"
77 #include "tree-dump.h"
82 #include "tree-pass.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
104   tree base;		/* Initial value of the iv.  */
105   tree base_object;	/* A memory object to that the induction variable points.  */
106   tree step;		/* Step of the iv (constant only).  */
107   tree ssa_name;	/* The ssa name with the value.  */
116   tree name;		/* The ssa name.  */
139   tree value;		/* For final value elimination, the expression for
150   tree stmt;		/* Statement in that it occurs.  */
151   tree *op_p;		/* The place where it occurs.  */
178   tree incremented_at;	/* For original biv, the statement where it is
180   tree var_before;	/* The variable used for it before increment.  */
181   tree var_after;	/* The variable used for it after increment.  */
313 static VEC(tree,heap) *decl_rtl_to_reset;
522 name_info (struct ivopts_data *data, tree name)
582 stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
601 stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
628 stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
649 abnormal_ssa_name_p (tree exp)
664 idx_contains_abnormal_ssa_name_p (tree base, tree *index,
682 contains_abnormal_ssa_name_p (tree expr)
736   tree niter;
759 /*  Returns tree describing number of iterations determined from
762 static tree
797 /* Returns tree describing number of iterations determined from
801 static tree
826   decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
832 static tree
833 determine_base_object (tree expr)
836   tree base, obj, op0, op1;
890 alloc_iv (tree base, tree step)
911 set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
925 get_iv (struct ivopts_data *data, tree var)
944 static tree
945 determine_biv_step (tree phi)
948   tree name = PHI_RESULT (phi);
965   tree phi, step, type, base;
1001   tree phi, var;
1032 find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
1034   tree lhs;
1061 find_givs_in_stmt (struct ivopts_data *data, tree stmt)
1113       tree niter = niter_for_single_dom_exit (data);
1137 record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
1138 	    tree stmt, enum use_type use_type)
1166 record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1191 find_interesting_uses_op (struct ivopts_data *data, tree op)
1195   tree stmt;
1237 find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1239   tree *op0_p;
1240   tree *op1_p;
1243   tree zero = integer_zero_node;
1299 expr_invariant_in_loop_p (struct loop *loop, tree expr)
1335   tree stmt;
1336   tree *step_p;
1340 idx_find_step (tree base, tree *idx, void *data)
1344   tree step, iv_base, iv_step, lbound, off;
1424 idx_record_use (tree base, tree *idx,
1439 may_be_unaligned_p (tree ref)
1441   tree base;
1442   tree base_type;
1445   tree toffset;
1475 may_be_nonaddressable_p (tree expr)
1505 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1507   tree base = *op_p, step = NULL;
1532       tree type = build_pointer_type (TREE_TYPE (base));
1533       tree astep;
1589 	  tree *ref = &TREE_OPERAND (base, 0);
1608 find_invariants_stmt (struct ivopts_data *data, tree stmt)
1612   tree op;
1624 find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1627   tree op, lhs, rhs;
1718   tree phi, def;
1734   tree phi;
1787 static tree
1788 strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
1791   tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
1793   tree type, orig_type = TREE_TYPE (expr);
1795   tree orig_expr = expr;
1924 static tree
1925 strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
1934 static tree
1935 generic_type_for (tree type)
1950 static tree
1951 find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
1977 		 tree base, tree step, bool important, enum iv_position pos,
1978 		 struct iv_use *use, tree incremented_at)
1982   tree type, orig_type;
2108 	       tree base, tree step, bool important, struct iv_use *use)
2124   tree type = lang_hooks.types.type_for_size (size, true);
2147   tree phi, def;
2195   tree base;
2338 		 bitmap depends_on, tree value)
2431 produce_memory_decl_rtl (tree obj, int *regno)
2450 static tree
2451 prepare_decl_rtl (tree *expr_p, int *ws, void *data)
2453   tree obj = NULL_TREE;
2498       VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
2508 computation_cost (tree expr)
2511   tree type = TREE_TYPE (expr);
2531 static tree
2532 var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
2544 tree_int_cst_sign_bit (tree t)
2566 constant_multiple_of (tree top, tree bot, double_int *mul)
2568   tree mby;
2628 aff_combination_const (struct affine_tree_combination *comb, tree type,
2644 aff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt)
2703 aff_combination_add_elt (struct affine_tree_combination *comb, tree elt,
2771 aff_combination_convert (tree type, struct affine_tree_combination *comb)
2802 tree_to_aff_combination (tree expr, tree type,
2807   tree cst, core, toffset;
2874 static tree
2875 add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
2917 /* Copies the tree elements of COMB to ensure that they are not shared.  */
2930 /* Makes tree from the affine combination COMB.  */
2932 static tree
2935   tree type = comb->type;
2936   tree expr = comb->rest;
2975 static tree
2976 fold_affine_expr (tree expr)
2978   tree type = TREE_TYPE (expr);
2993 static tree
2994 determine_common_wider_type (tree *a, tree *b)
2996   tree wider_type = NULL;
2997   tree suba, subb;
2998   tree atype = TREE_TYPE (*a);
3032 		     struct iv_use *use, struct iv_cand *cand, tree at,
3035   tree ubase = use->iv->base;
3036   tree ustep = use->iv->step;
3037   tree cbase = cand->iv->base;
3038   tree cstep = cand->iv->step;
3039   tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
3040   tree common_type;
3041   tree uutype;
3042   tree expr, delta;
3043   tree ratio;
3047   tree cstep_orig = cstep, ustep_orig = ustep;
3197 static tree
3199 		    struct iv_use *use, struct iv_cand *cand, tree at)
3202   tree type = TREE_TYPE (use->iv->base);
3213 static tree
3565 force_expr_to_var_cost (tree expr)
3571   tree op0, op1;
3577       tree var = create_tmp_var_raw (integer_type_node, "test_var");
3580       tree addr;
3581       tree type = build_pointer_type (integer_type_node);
3620 	  tree obj = TREE_OPERAND (expr, 0);
3694 		tree expr, bitmap *depends_on)
3712 		    tree addr, bool *symbol_present, bool *var_present,
3715   tree core;
3718   tree toffset;
3758 		     tree e1, tree e2, bool *symbol_present, bool *var_present,
3796 		 tree e1, tree e2, bool *symbol_present, bool *var_present,
3848 			 bool address_p, bitmap *depends_on, tree at)
3850   tree ubase = use->iv->base, ustep = use->iv->step;
3851   tree cbase, cstep;
3852   tree utype = TREE_TYPE (ubase), ctype;
3992     tree comp = get_computation_at (data->current_loop, use, cand, at);
4062 static tree
4063 iv_value (struct iv *iv, tree niter)
4065   tree val;
4066   tree type = TREE_TYPE (iv->base);
4076 static tree
4077 cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
4079   tree val = iv_value (cand->iv, niter);
4080   tree type = TREE_TYPE (cand->iv->base);
4090 static tree
4093   tree step = iv->step, period, type;
4094   tree pow2div;
4133 		  struct iv_use *use, struct iv_cand *cand, tree *bound)
4137   tree nit, nit_type;
4138   tree wider_type, period, per_type;
4194   tree bound = NULL_TREE, op, cond;
4340   tree base;
4413   tree phi, op;
5279   tree base;
5337 remove_statement (tree stmt, bool including_defined_name)
5363   tree comp;
5364   tree op, stmts, tgt, ass;
5374       tree step, ctype, utype;
5474 idx_remove_ssa_names (tree base, tree *idx,
5477   tree *op;
5499 static tree
5500 unshare_and_remove_ssa_names (tree ref)
5515 static tree
5516 get_ref_tag (tree ref, tree orig)
5518   tree var = get_base_address (ref);
5519   tree aref = NULL_TREE, tag, sv;
5571 copy_ref_info (tree new_ref, tree old_ref)
5590   tree ref;
5607   tree comp;
5608   tree *op_p, cond, op, stmts, bound;
5616       tree var = var_at_stmt (data->current_loop, cand, use->stmt);
5617       tree var_type = TREE_TYPE (var);
5723   tree obj;
5777   for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++)
5780   VEC_truncate (tree, decl_rtl_to_reset, 0);
5784    loop tree.  */
5795   VEC_free (tree, heap, decl_rtl_to_reset);