1 | /* Chains of recurrences. |
---|---|

2 | Copyright (C) 2003-2017 Free Software Foundation, Inc. |

3 | Contributed by Sebastian Pop <pop@cri.ensmp.fr> |

4 | |

5 | This file is part of GCC. |

6 | |

7 | GCC is free software; you can redistribute it and/or modify it under |

8 | the terms of the GNU General Public License as published by the Free |

9 | Software Foundation; either version 3, or (at your option) any later |

10 | version. |

11 | |

12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |

13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |

14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |

15 | for more details. |

16 | |

17 | You should have received a copy of the GNU General Public License |

18 | along with GCC; see the file COPYING3. If not see |

19 | <http://www.gnu.org/licenses/>. */ |

20 | |

21 | #ifndef GCC_TREE_CHREC_H |

22 | #define GCC_TREE_CHREC_H |

23 | |

24 | /* The following trees are unique elements. Thus the comparison of another |

25 | element to these elements should be done on the pointer to these trees, |

26 | and not on their value. */ |

27 | |

28 | extern tree chrec_not_analyzed_yet; |

29 | extern GTY(()) tree chrec_dont_know; |

30 | extern GTY(()) tree chrec_known; |

31 | |

32 | /* After having added an automatically generated element, please |

33 | include it in the following function. */ |

34 | |

35 | static inline bool |

36 | automatically_generated_chrec_p (const_tree chrec) |

37 | { |

38 | return (chrec == chrec_dont_know |

39 | || chrec == chrec_known); |

40 | } |

41 | |

42 | /* The tree nodes aka. CHRECs. */ |

43 | |

44 | static inline bool |

45 | tree_is_chrec (const_tree expr) |

46 | { |

47 | if (TREE_CODE (expr) == POLYNOMIAL_CHREC |

48 | || automatically_generated_chrec_p (expr)) |

49 | return true; |

50 | else |

51 | return false; |

52 | } |

53 | |

54 | |

55 | enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN}; |

56 | enum ev_direction scev_direction (const_tree); |

57 | |

58 | /* Chrec folding functions. */ |

59 | extern tree chrec_fold_plus (tree, tree, tree); |

60 | extern tree chrec_fold_minus (tree, tree, tree); |

61 | extern tree chrec_fold_multiply (tree, tree, tree); |

62 | extern tree chrec_convert (tree, tree, gimple *, bool = true, tree = NULL); |

63 | extern tree chrec_convert_rhs (tree, tree, gimple *); |

64 | extern tree chrec_convert_aggressive (tree, tree, bool *); |

65 | |

66 | /* Operations. */ |

67 | extern tree chrec_apply (unsigned, tree, tree); |

68 | extern tree chrec_apply_map (tree, vec<tree> ); |

69 | extern tree chrec_replace_initial_condition (tree, tree); |

70 | extern tree initial_condition (tree); |

71 | extern tree initial_condition_in_loop_num (tree, unsigned); |

72 | extern tree evolution_part_in_loop_num (tree, unsigned); |

73 | extern tree hide_evolution_in_other_loops_than_loop (tree, unsigned); |

74 | extern tree reset_evolution_in_loop (unsigned, tree, tree); |

75 | extern tree chrec_merge (tree, tree); |

76 | extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *); |

77 | extern bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple *, |

78 | bool, tree = NULL); |

79 | |

80 | /* Observers. */ |

81 | extern bool eq_evolutions_p (const_tree, const_tree); |

82 | extern bool is_multivariate_chrec (const_tree); |

83 | extern bool chrec_contains_symbols (const_tree); |

84 | extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned); |

85 | extern bool chrec_contains_undetermined (const_tree); |

86 | extern bool tree_contains_chrecs (const_tree, int *); |

87 | extern bool evolution_function_is_affine_multivariate_p (const_tree, int); |

88 | extern bool evolution_function_is_univariate_p (const_tree); |

89 | extern unsigned nb_vars_in_chrec (tree); |

90 | extern bool evolution_function_is_invariant_p (tree, int); |

91 | extern bool scev_is_linear_expression (tree); |

92 | extern bool evolution_function_right_is_integer_cst (const_tree); |

93 | |

94 | /* Determines whether CHREC is equal to zero. */ |

95 | |

96 | static inline bool |

97 | chrec_zerop (const_tree chrec) |

98 | { |

99 | if (chrec == NULL_TREE) |

100 | return false; |

101 | |

102 | if (TREE_CODE (chrec) == INTEGER_CST) |

103 | return integer_zerop (chrec); |

104 | |

105 | return false; |

106 | } |

107 | |

108 | /* Determines whether CHREC is a loop invariant with respect to LOOP_NUM. |

109 | Set the result in RES and return true when the property can be computed. */ |

110 | |

111 | static inline bool |

112 | no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res) |

113 | { |

114 | tree scev; |

115 | |

116 | if (chrec == chrec_not_analyzed_yet |

117 | || chrec == chrec_dont_know |

118 | || chrec_contains_symbols_defined_in_loop (chrec, loop_num)) |

119 | return false; |

120 | |

121 | STRIP_NOPS (chrec); |

122 | scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num); |

123 | *res = !tree_contains_chrecs (scev, NULL); |

124 | return true; |

125 | } |

126 | |

127 | /* Build a polynomial chain of recurrence. */ |

128 | |

129 | static inline tree |

130 | build_polynomial_chrec (unsigned loop_num, |

131 | tree left, |

132 | tree right) |

133 | { |

134 | bool val; |

135 | |

136 | if (left == chrec_dont_know |

137 | || right == chrec_dont_know) |

138 | return chrec_dont_know; |

139 | |

140 | if (!no_evolution_in_loop_p (left, loop_num, &val) |

141 | || !val) |

142 | return chrec_dont_know; |

143 | |

144 | /* Types of left and right sides of a chrec should be compatible, but |

145 | pointer CHRECs are special in that the evolution is of ptroff type. */ |

146 | if (POINTER_TYPE_P (TREE_TYPE (left))) |

147 | gcc_checking_assert (ptrofftype_p (TREE_TYPE (right))); |

148 | else |

149 | { |

150 | /* Pointer types should occur only on the left hand side, i.e. in |

151 | the base of the chrec, and not in the step. */ |

152 | gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (right)) |

153 | && types_compatible_p (TREE_TYPE (left), |

154 | TREE_TYPE (right))); |

155 | } |

156 | |

157 | if (chrec_zerop (right)) |

158 | return left; |

159 | |

160 | tree chrec = build2 (POLYNOMIAL_CHREC, TREE_TYPE (left), left, right); |

161 | CHREC_VARIABLE (chrec) = loop_num; |

162 | return chrec; |

163 | } |

164 | |

165 | /* Determines whether the expression CHREC is a constant. */ |

166 | |

167 | static inline bool |

168 | evolution_function_is_constant_p (const_tree chrec) |

169 | { |

170 | if (chrec == NULL_TREE) |

171 | return false; |

172 | |

173 | if (CONSTANT_CLASS_P (chrec)) |

174 | return true; |

175 | return is_gimple_min_invariant (chrec); |

176 | } |

177 | |

178 | /* Determine whether CHREC is an affine evolution function in LOOPNUM. */ |

179 | |

180 | static inline bool |

181 | evolution_function_is_affine_in_loop (const_tree chrec, int loopnum) |

182 | { |

183 | if (chrec == NULL_TREE) |

184 | return false; |

185 | |

186 | switch (TREE_CODE (chrec)) |

187 | { |

188 | case POLYNOMIAL_CHREC: |

189 | if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), loopnum) |

190 | && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), loopnum)) |

191 | return true; |

192 | else |

193 | return false; |

194 | |

195 | default: |

196 | return false; |

197 | } |

198 | } |

199 | |

200 | /* Determine whether CHREC is an affine evolution function or not. */ |

201 | |

202 | static inline bool |

203 | evolution_function_is_affine_p (const_tree chrec) |

204 | { |

205 | return chrec |

206 | && TREE_CODE (chrec) == POLYNOMIAL_CHREC |

207 | && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), |

208 | CHREC_VARIABLE (chrec)) |

209 | && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC |

210 | || evolution_function_is_affine_p (CHREC_RIGHT (chrec))); |

211 | } |

212 | |

213 | /* Determines whether EXPR does not contains chrec expressions. */ |

214 | |

215 | static inline bool |

216 | tree_does_not_contain_chrecs (const_tree expr) |

217 | { |

218 | return !tree_contains_chrecs (expr, NULL); |

219 | } |

220 | |

221 | /* Returns the type of the chrec. */ |

222 | |

223 | static inline tree |

224 | chrec_type (const_tree chrec) |

225 | { |

226 | if (automatically_generated_chrec_p (chrec)) |

227 | return NULL_TREE; |

228 | |

229 | return TREE_TYPE (chrec); |

230 | } |

231 | |

232 | static inline tree |

233 | chrec_fold_op (enum tree_code code, tree type, tree op0, tree op1) |

234 | { |

235 | switch (code) |

236 | { |

237 | case PLUS_EXPR: |

238 | return chrec_fold_plus (type, op0, op1); |

239 | |

240 | case MINUS_EXPR: |

241 | return chrec_fold_minus (type, op0, op1); |

242 | |

243 | case MULT_EXPR: |

244 | return chrec_fold_multiply (type, op0, op1); |

245 | |

246 | default: |

247 | gcc_unreachable (); |

248 | } |

249 | |

250 | } |

251 | |

252 | #endif /* GCC_TREE_CHREC_H */ |

253 |