1 | /* RTL iterators |
---|---|

2 | Copyright (C) 2014-2017 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 under |

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

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

9 | version. |

10 | |

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

12 | 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 | /* This structure describes the subrtxes of an rtx as follows: |

21 | |

22 | - if the rtx has no subrtxes, START and COUNT are both 0. |

23 | |

24 | - if all the subrtxes of an rtx are stored in a contiguous block |

25 | of XEXPs ("e"s), START is the index of the first XEXP and COUNT |

26 | is the number of them. |

27 | |

28 | - otherwise START is arbitrary and COUNT is UCHAR_MAX. |

29 | |

30 | rtx_all_subrtx_bounds applies to all codes. rtx_nonconst_subrtx_bounds |

31 | is like rtx_all_subrtx_bounds except that all constant rtxes are treated |

32 | as having no subrtxes. */ |

33 | struct rtx_subrtx_bound_info { |

34 | unsigned char start; |

35 | unsigned char count; |

36 | }; |

37 | extern rtx_subrtx_bound_info rtx_all_subrtx_bounds[]; |

38 | extern rtx_subrtx_bound_info rtx_nonconst_subrtx_bounds[]; |

39 | |

40 | /* Return true if CODE has no subrtxes. */ |

41 | |

42 | static inline bool |

43 | leaf_code_p (enum rtx_code code) |

44 | { |

45 | return rtx_all_subrtx_bounds[code].count == 0; |

46 | } |

47 | |

48 | /* Used to iterate over subrtxes of an rtx. T abstracts the type of |

49 | access. */ |

50 | template <typename T> |

51 | class generic_subrtx_iterator |

52 | { |

53 | static const size_t LOCAL_ELEMS = 16; |

54 | typedef typename T::value_type value_type; |

55 | typedef typename T::rtx_type rtx_type; |

56 | typedef typename T::rtunion_type rtunion_type; |

57 | |

58 | public: |

59 | struct array_type |

60 | { |

61 | array_type (); |

62 | ~array_type (); |

63 | value_type stack[LOCAL_ELEMS]; |

64 | vec <value_type, va_heap, vl_embed> *heap; |

65 | }; |

66 | generic_subrtx_iterator (array_type &, value_type, |

67 | const rtx_subrtx_bound_info *); |

68 | |

69 | value_type operator * () const; |

70 | bool at_end () const; |

71 | void next (); |

72 | void skip_subrtxes (); |

73 | void substitute (value_type); |

74 | |

75 | private: |

76 | /* The bounds to use for iterating over subrtxes. */ |

77 | const rtx_subrtx_bound_info *m_bounds; |

78 | |

79 | /* The storage used for the worklist. */ |

80 | array_type &m_array; |

81 | |

82 | /* The current rtx. */ |

83 | value_type m_current; |

84 | |

85 | /* The base of the current worklist. */ |

86 | value_type *m_base; |

87 | |

88 | /* The number of subrtxes in M_BASE. */ |

89 | size_t m_end; |

90 | |

91 | /* The following booleans shouldn't end up in registers or memory |

92 | but just direct control flow. */ |

93 | |

94 | /* True if the iteration is over. */ |

95 | bool m_done; |

96 | |

97 | /* True if we should skip the subrtxes of M_CURRENT. */ |

98 | bool m_skip; |

99 | |

100 | /* True if M_CURRENT has been replaced with a different rtx. */ |

101 | bool m_substitute; |

102 | |

103 | static void free_array (array_type &); |

104 | static size_t add_subrtxes_to_queue (array_type &, value_type *, size_t, |

105 | rtx_type); |

106 | static value_type *add_single_to_queue (array_type &, value_type *, size_t, |

107 | value_type); |

108 | }; |

109 | |

110 | template <typename T> |

111 | inline generic_subrtx_iterator <T>::array_type::array_type () : heap (0) {} |

112 | |

113 | template <typename T> |

114 | inline generic_subrtx_iterator <T>::array_type::~array_type () |

115 | { |

116 | if (__builtin_expect (heap != 0, false)) |

117 | free_array (*this); |

118 | } |

119 | |

120 | /* Iterate over X and its subrtxes, in arbitrary order. Use ARRAY to |

121 | store the worklist. We use an external array in order to avoid |

122 | capturing the fields of this structure when taking the address of |

123 | the array. Use BOUNDS to find the bounds of simple "e"-string codes. */ |

124 | |

125 | template <typename T> |

126 | inline generic_subrtx_iterator <T>:: |

127 | generic_subrtx_iterator (array_type &array, value_type x, |

128 | const rtx_subrtx_bound_info *bounds) |

129 | : m_bounds (bounds), |

130 | m_array (array), |

131 | m_current (x), |

132 | m_base (m_array.stack), |

133 | m_end (0), |

134 | m_done (false), |

135 | m_skip (false), |

136 | m_substitute (false) |

137 | { |

138 | } |

139 | |

140 | /* Return the current subrtx. */ |

141 | |

142 | template <typename T> |

143 | inline typename T::value_type |

144 | generic_subrtx_iterator <T>::operator * () const |

145 | { |

146 | return m_current; |

147 | } |

148 | |

149 | /* Return true if the iteration has finished. */ |

150 | |

151 | template <typename T> |

152 | inline bool |

153 | generic_subrtx_iterator <T>::at_end () const |

154 | { |

155 | return m_done; |

156 | } |

157 | |

158 | /* Move on to the next subrtx. */ |

159 | |

160 | template <typename T> |

161 | inline void |

162 | generic_subrtx_iterator <T>::next () |

163 | { |

164 | if (m_substitute) |

165 | { |

166 | m_substitute = false; |

167 | m_skip = false; |

168 | return; |

169 | } |

170 | if (!m_skip) |

171 | { |

172 | /* Add the subrtxes of M_CURRENT. */ |

173 | rtx_type x = T::get_rtx (m_current); |

174 | if (__builtin_expect (x != 0, true)) |

175 | { |

176 | enum rtx_code code = GET_CODE (x); |

177 | ssize_t count = m_bounds[code].count; |

178 | if (count > 0) |

179 | { |

180 | /* Handle the simple case of a single "e" block that is known |

181 | to fit into the current array. */ |

182 | if (__builtin_expect (m_end + count <= LOCAL_ELEMS + 1, true)) |

183 | { |

184 | /* Set M_CURRENT to the first subrtx and queue the rest. */ |

185 | ssize_t start = m_bounds[code].start; |

186 | rtunion_type *src = &x->u.fld[start]; |

187 | if (__builtin_expect (count > 2, false)) |

188 | m_base[m_end++] = T::get_value (src[2].rt_rtx); |

189 | if (count > 1) |

190 | m_base[m_end++] = T::get_value (src[1].rt_rtx); |

191 | m_current = T::get_value (src[0].rt_rtx); |

192 | return; |

193 | } |

194 | /* Handle cases which aren't simple "e" sequences or where |

195 | the sequence might overrun M_BASE. */ |

196 | count = add_subrtxes_to_queue (m_array, m_base, m_end, x); |

197 | if (count > 0) |

198 | { |

199 | m_end += count; |

200 | if (m_end > LOCAL_ELEMS) |

201 | m_base = m_array.heap->address (); |

202 | m_current = m_base[--m_end]; |

203 | return; |

204 | } |

205 | } |

206 | } |

207 | } |

208 | else |

209 | m_skip = false; |

210 | if (m_end == 0) |

211 | m_done = true; |

212 | else |

213 | m_current = m_base[--m_end]; |

214 | } |

215 | |

216 | /* Skip the subrtxes of the current rtx. */ |

217 | |

218 | template <typename T> |

219 | inline void |

220 | generic_subrtx_iterator <T>::skip_subrtxes () |

221 | { |

222 | m_skip = true; |

223 | } |

224 | |

225 | /* Ignore the subrtxes of the current rtx and look at X instead. */ |

226 | |

227 | template <typename T> |

228 | inline void |

229 | generic_subrtx_iterator <T>::substitute (value_type x) |

230 | { |

231 | m_substitute = true; |

232 | m_current = x; |

233 | } |

234 | |

235 | /* Iterators for const_rtx. */ |

236 | struct const_rtx_accessor |

237 | { |

238 | typedef const_rtx value_type; |

239 | typedef const_rtx rtx_type; |

240 | typedef const rtunion rtunion_type; |

241 | static rtx_type get_rtx (value_type x) { return x; } |

242 | static value_type get_value (rtx_type x) { return x; } |

243 | }; |

244 | typedef generic_subrtx_iterator <const_rtx_accessor> subrtx_iterator; |

245 | |

246 | /* Iterators for non-constant rtx. */ |

247 | struct rtx_var_accessor |

248 | { |

249 | typedef rtx value_type; |

250 | typedef rtx rtx_type; |

251 | typedef rtunion rtunion_type; |

252 | static rtx_type get_rtx (value_type x) { return x; } |

253 | static value_type get_value (rtx_type x) { return x; } |

254 | }; |

255 | typedef generic_subrtx_iterator <rtx_var_accessor> subrtx_var_iterator; |

256 | |

257 | /* Iterators for rtx *. */ |

258 | struct rtx_ptr_accessor |

259 | { |

260 | typedef rtx *value_type; |

261 | typedef rtx rtx_type; |

262 | typedef rtunion rtunion_type; |

263 | static rtx_type get_rtx (value_type ptr) { return *ptr; } |

264 | static value_type get_value (rtx_type &x) { return &x; } |

265 | }; |

266 | typedef generic_subrtx_iterator <rtx_ptr_accessor> subrtx_ptr_iterator; |

267 | |

268 | #define ALL_BOUNDS rtx_all_subrtx_bounds |

269 | #define NONCONST_BOUNDS rtx_nonconst_subrtx_bounds |

270 | |

271 | /* Use ITER to iterate over const_rtx X and its recursive subrtxes, |

272 | using subrtx_iterator::array ARRAY as the storage for the worklist. |

273 | ARRAY can be reused for multiple consecutive iterations but shouldn't |

274 | be shared by two concurrent iterations. TYPE is ALL if all subrtxes |

275 | are of interest or NONCONST if it is safe to ignore subrtxes of |

276 | constants. */ |

277 | #define FOR_EACH_SUBRTX(ITER, ARRAY, X, TYPE) \ |

278 | for (subrtx_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \ |

279 | ITER.next ()) |

280 | |

281 | /* Like FOR_EACH_SUBRTX, but iterate over subrtxes of an rtx X. */ |

282 | #define FOR_EACH_SUBRTX_VAR(ITER, ARRAY, X, TYPE) \ |

283 | for (subrtx_var_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \ |

284 | ITER.next ()) |

285 | |

286 | /* Like FOR_EACH_SUBRTX, but iterate over subrtx pointers of rtx pointer X. |

287 | For example, if X is &PATTERN (insn) and the pattern is a SET, iterate |

288 | over &PATTERN (insn), &SET_DEST (PATTERN (insn)), etc. */ |

289 | #define FOR_EACH_SUBRTX_PTR(ITER, ARRAY, X, TYPE) \ |

290 | for (subrtx_ptr_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \ |

291 | ITER.next ()) |

292 |