diff options
Diffstat (limited to 'gcc/tree-affine.c')
| -rw-r--r-- | gcc/tree-affine.c | 211 |
1 files changed, 211 insertions, 0 deletions
diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c index 43b251d..87f379c 100644 --- a/gcc/tree-affine.c +++ b/gcc/tree-affine.c @@ -29,7 +29,9 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "output.h" #include "diagnostic.h" #include "tree-dump.h" +#include "pointer-set.h" #include "tree-affine.h" +#include "tree-gimple.h" /* Extends CST as appropriate for the affine combinations COMB. */ @@ -493,3 +495,212 @@ aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r) aff_combination_add_product (c1, double_int_one, c2->rest, r); aff_combination_add_product (c1, c2->offset, NULL, r); } + +/* Returns the element of COMB whose value is VAL, or NULL if no such + element exists. If IDX is not NULL, it is set to the index of VAL in + COMB. */ + +static struct aff_comb_elt * +aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx) +{ + unsigned i; + + for (i = 0; i < comb->n; i++) + if (operand_equal_p (comb->elts[i].val, val, 0)) + { + if (idx) + *idx = i; + + return &comb->elts[i]; + } + + return NULL; +} + +/* Element of the cache that maps ssa name NAME to its expanded form + as an affine expression EXPANSION. */ + +struct name_expansion +{ + aff_tree expansion; + + /* True if the expansion for the name is just being generated. */ + unsigned in_progress : 1; +}; + +/* Similar to tree_to_aff_combination, but follows SSA name definitions + and expands them recursively. CACHE is used to cache the expansions + of the ssa names, to avoid exponential time complexity for cases + like + + a1 = a0 + a0; + a2 = a1 + a1; + a3 = a2 + a2; + ... */ + +void +tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb, + struct pointer_map_t **cache) +{ + unsigned i; + aff_tree to_add, current, curre; + tree e, def, rhs; + double_int scale; + void **slot; + struct name_expansion *exp; + + tree_to_aff_combination (expr, type, comb); + aff_combination_zero (&to_add, type); + for (i = 0; i < comb->n; i++) + { + e = comb->elts[i].val; + if (TREE_CODE (e) != SSA_NAME) + continue; + def = SSA_NAME_DEF_STMT (e); + if (TREE_CODE (def) != GIMPLE_MODIFY_STMT + || GIMPLE_STMT_OPERAND (def, 0) != e) + continue; + + rhs = GIMPLE_STMT_OPERAND (def, 1); + if (TREE_CODE (rhs) != SSA_NAME + && !EXPR_P (rhs) + && !is_gimple_min_invariant (rhs)) + continue; + + /* We do not know whether the reference retains its value at the + place where the expansion is used. */ + if (REFERENCE_CLASS_P (rhs)) + continue; + + if (!*cache) + *cache = pointer_map_create (); + slot = pointer_map_insert (*cache, e); + exp = *slot; + + if (!exp) + { + exp = XNEW (struct name_expansion); + exp->in_progress = 1; + *slot = exp; + tree_to_aff_combination_expand (rhs, type, ¤t, cache); + exp->expansion = current; + exp->in_progress = 0; + } + else + { + /* Since we follow the definitions in the SSA form, we should not + enter a cycle unless we pass through a phi node. */ + gcc_assert (!exp->in_progress); + current = exp->expansion; + } + + /* Accumulate the new terms to TO_ADD, so that we do not modify + COMB while traversing it; include the term -coef * E, to remove + it from COMB. */ + scale = comb->elts[i].coef; + aff_combination_zero (&curre, type); + aff_combination_add_elt (&curre, e, double_int_neg (scale)); + aff_combination_scale (¤t, scale); + aff_combination_add (&to_add, ¤t); + aff_combination_add (&to_add, &curre); + } + aff_combination_add (comb, &to_add); +} + +/* Frees memory occupied by struct name_expansion in *VALUE. Callback for + pointer_map_traverse. */ + +static bool +free_name_expansion (void *key ATTRIBUTE_UNUSED, void **value, + void *data ATTRIBUTE_UNUSED) +{ + struct name_expansion *exp = *value; + + free (exp); + return true; +} + +/* Frees memory allocated for the CACHE used by + tree_to_aff_combination_expand. */ + +void +free_affine_expand_cache (struct pointer_map_t **cache) +{ + if (!*cache) + return; + + pointer_map_traverse (*cache, free_name_expansion, NULL); + pointer_map_destroy (*cache); + *cache = NULL; +} + +/* If VAL != CST * DIV for any constant CST, returns false. + Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true, + additionally compares CST and MULT, and if they are different, + returns false. Finally, if neither of these two cases occcur, + true is returned, and if CST != 0, CST is stored to MULT and + MULT_SET is set to true. */ + +static bool +double_int_constant_multiple_p (double_int val, double_int div, + bool *mult_set, double_int *mult) +{ + double_int rem, cst; + + if (double_int_zero_p (val)) + return true; + + if (double_int_zero_p (div)) + return false; + + cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem); + if (!double_int_zero_p (rem)) + return false; + + if (*mult_set && !double_int_equal_p (*mult, cst)) + return false; + + *mult_set = true; + *mult = cst; + return true; +} + +/* Returns true if VAL = X * DIV for some constant X. If this is the case, + X is stored to MULT. */ + +bool +aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div, + double_int *mult) +{ + bool mult_set = false; + unsigned i; + + if (val->n == 0 && double_int_zero_p (val->offset)) + { + *mult = double_int_zero; + return true; + } + if (val->n != div->n) + return false; + + if (val->rest || div->rest) + return false; + + if (!double_int_constant_multiple_p (val->offset, div->offset, + &mult_set, mult)) + return false; + + for (i = 0; i < div->n; i++) + { + struct aff_comb_elt *elt + = aff_combination_find_elt (val, div->elts[i].val, NULL); + if (!elt) + return false; + if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef, + &mult_set, mult)) + return false; + } + + gcc_assert (mult_set); + return true; +} |