1 /* Operations with affine combinations of trees. 2 Copyright (C) 2005-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 3, or (at your option) any 9 later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 /* Affine combination of trees. We keep track of at most MAX_AFF_ELTS elements 21 to make things simpler; this is sufficient in most cases. */ 22 23 #ifndef GCC_TREE_AFFINE_H 24 #define GCC_TREE_AFFINE_H 25 26 27 #define MAX_AFF_ELTS 8 28 29 /* Element of an affine combination. */ 30 31 struct aff_comb_elt 32 { 33 /* The value of the element. */ 34 tree val; 35 36 /* Its coefficient in the combination. */ 37 widest_int coef; 38 }; 39 40 struct aff_tree 41 { 42 /* Type of the result of the combination. */ 43 tree type; 44 45 /* Constant offset. */ 46 poly_widest_int offset; 47 48 /* Number of elements of the combination. */ 49 unsigned n; 50 51 /* Elements and their coefficients. Type of elements may be different from 52 TYPE, but their sizes must be the same (STRIP_NOPS is applied to the 53 elements). 54 55 The coefficients are always sign extended from the precision of TYPE 56 (regardless of signedness of TYPE). */ 57 struct aff_comb_elt elts[MAX_AFF_ELTS]; 58 59 /* Remainder of the expression. Usually NULL, used only if there are more 60 than MAX_AFF_ELTS elements. Type of REST will be either sizetype for 61 TYPE of POINTER_TYPEs or TYPE. */ 62 tree rest; 63 }; 64 65 struct name_expansion; 66 67 void aff_combination_const (aff_tree *, tree, const poly_widest_int &); 68 void aff_combination_elt (aff_tree *, tree, tree); 69 void aff_combination_scale (aff_tree *, const widest_int &); 70 void aff_combination_mult (aff_tree *, aff_tree *, aff_tree *); 71 void aff_combination_add (aff_tree *, aff_tree *); 72 void aff_combination_add_elt (aff_tree *, tree, const widest_int &); 73 void aff_combination_remove_elt (aff_tree *, unsigned); 74 void aff_combination_convert (aff_tree *, tree); 75 void tree_to_aff_combination (tree, tree, aff_tree *); 76 tree aff_combination_to_tree (aff_tree *); 77 void unshare_aff_combination (aff_tree *); 78 bool aff_combination_constant_multiple_p (aff_tree *, aff_tree *, 79 poly_widest_int *); 80 void aff_combination_expand (aff_tree *, hash_map<tree, name_expansion *> **); 81 void tree_to_aff_combination_expand (tree, tree, aff_tree *, 82 hash_map<tree, name_expansion *> **); 83 tree get_inner_reference_aff (tree, aff_tree *, poly_widest_int *); 84 void free_affine_expand_cache (hash_map<tree, name_expansion *> **); 85 bool aff_comb_cannot_overlap_p (aff_tree *, const poly_widest_int &, 86 const poly_widest_int &); 87 88 /* Debugging functions. */ 89 void debug_aff (aff_tree *); 90 91 /* Return AFF's type. */ 92 inline tree 93 aff_combination_type (aff_tree *aff) 94 { 95 return aff->type; 96 } 97 98 /* Return true if AFF is actually ZERO. */ 99 inline bool 100 aff_combination_zero_p (aff_tree *aff) 101 { 102 if (!aff) 103 return true; 104 105 if (aff->n == 0 && known_eq (aff->offset, 0)) 106 return true; 107 108 return false; 109 } 110 111 /* Return true if AFF is actually const. */ 112 inline bool 113 aff_combination_const_p (aff_tree *aff) 114 { 115 return (aff == NULL || aff->n == 0); 116 } 117 118 /* Return true iff AFF contains one (negated) singleton variable. Users need 119 to make sure AFF points to a valid combination. */ 120 inline bool 121 aff_combination_singleton_var_p (aff_tree *aff) 122 { 123 return (aff->n == 1 124 && known_eq (aff->offset, 0) 125 && (aff->elts[0].coef == 1 || aff->elts[0].coef == -1)); 126 } 127 #endif /* GCC_TREE_AFFINE_H */ 128