Warning: That file was not part of the compilation database. It may have many parsing errors.

1 | /* A class for building vector constant patterns. |
---|---|

2 | Copyright (C) 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 | #ifndef GCC_VECTOR_BUILDER_H |

21 | #define GCC_VECTOR_BUILDER_H |

22 | |

23 | /* This class is a wrapper around auto_vec<T> for building vectors of T. |

24 | It aims to encode each vector as npatterns interleaved patterns, |

25 | where each pattern represents a sequence: |

26 | |

27 | { BASE0, BASE1, BASE1 + STEP, BASE1 + STEP*2, BASE1 + STEP*3, ... } |

28 | |

29 | The first three elements in each pattern provide enough information |

30 | to derive the other elements. If all patterns have a STEP of zero, |

31 | we only need to encode the first two elements in each pattern. |

32 | If BASE1 is also equal to BASE0 for all patterns, we only need to |

33 | encode the first element in each pattern. The number of encoded |

34 | elements per pattern is given by nelts_per_pattern. |

35 | |

36 | The class can be used in two ways: |

37 | |

38 | 1. It can be used to build a full image of the vector, which is then |

39 | canonicalized by finalize (). In this case npatterns is initially |

40 | the number of elements in the vector and nelts_per_pattern is |

41 | initially 1. |

42 | |

43 | 2. It can be used to build a vector that already has a known encoding. |

44 | This is preferred since it is more efficient and copes with |

45 | variable-length vectors. finalize () then canonicalizes the encoding |

46 | to a simpler form if possible. |

47 | |

48 | The derived class Derived provides this functionality for specific Ts. |

49 | Derived needs to provide the following interface: |

50 | |

51 | bool equal_p (T elt1, T elt2) const; |

52 | |

53 | Return true if elements ELT1 and ELT2 are equal. |

54 | |

55 | bool allow_steps_p () const; |

56 | |

57 | Return true if a stepped representation is OK. We don't allow |

58 | linear series for anything other than integers, to avoid problems |

59 | with rounding. |

60 | |

61 | bool integral_p (T elt) const; |

62 | |

63 | Return true if element ELT can be interpreted as an integer. |

64 | |

65 | StepType step (T elt1, T elt2) const; |

66 | |

67 | Return the value of element ELT2 minus the value of element ELT1, |

68 | given integral_p (ELT1) && integral_p (ELT2). There is no fixed |

69 | choice of StepType. |

70 | |

71 | T apply_step (T base, unsigned int factor, StepType step) const; |

72 | |

73 | Return a vector element with the value BASE + FACTOR * STEP. |

74 | |

75 | bool can_elide_p (T elt) const; |

76 | |

77 | Return true if we can drop element ELT, even if the retained |

78 | elements are different. This is provided for TREE_OVERFLOW |

79 | handling. |

80 | |

81 | void note_representative (T *elt1_ptr, T elt2); |

82 | |

83 | Record that ELT2 is being elided, given that ELT1_PTR points to |

84 | the last encoded element for the containing pattern. This is |

85 | again provided for TREE_OVERFLOW handling. */ |

86 | |

87 | template<typename T, typename Derived> |

88 | class vector_builder : public auto_vec<T, 32> |

89 | { |

90 | public: |

91 | vector_builder (); |

92 | |

93 | unsigned int full_nelts () const { return m_full_nelts; } |

94 | unsigned int npatterns () const { return m_npatterns; } |

95 | unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; } |

96 | unsigned int encoded_nelts () const; |

97 | bool encoded_full_vector_p () const; |

98 | T elt (unsigned int) const; |

99 | |

100 | void finalize (); |

101 | |

102 | protected: |

103 | void new_vector (unsigned int, unsigned int, unsigned int); |

104 | void reshape (unsigned int, unsigned int); |

105 | bool repeating_sequence_p (unsigned int, unsigned int, unsigned int); |

106 | bool stepped_sequence_p (unsigned int, unsigned int, unsigned int); |

107 | bool try_npatterns (unsigned int); |

108 | |

109 | private: |

110 | vector_builder (const vector_builder &); |

111 | vector_builder &operator= (const vector_builder &); |

112 | Derived *derived () { return static_cast<Derived *> (this); } |

113 | const Derived *derived () const; |

114 | |

115 | unsigned int m_full_nelts; |

116 | unsigned int m_npatterns; |

117 | unsigned int m_nelts_per_pattern; |

118 | }; |

119 | |

120 | template<typename T, typename Derived> |

121 | inline const Derived * |

122 | vector_builder<T, Derived>::derived () const |

123 | { |

124 | return static_cast<const Derived *> (this); |

125 | } |

126 | |

127 | template<typename T, typename Derived> |

128 | inline |

129 | vector_builder<T, Derived>::vector_builder () |

130 | : m_full_nelts (0), |

131 | m_npatterns (0), |

132 | m_nelts_per_pattern (0) |

133 | {} |

134 | |

135 | /* Return the number of elements that are explicitly encoded. The vec |

136 | starts with these explicitly-encoded elements and may contain additional |

137 | elided elements. */ |

138 | |

139 | template<typename T, typename Derived> |

140 | inline unsigned int |

141 | vector_builder<T, Derived>::encoded_nelts () const |

142 | { |

143 | return m_npatterns * m_nelts_per_pattern; |

144 | } |

145 | |

146 | /* Return true if every element of the vector is explicitly encoded. */ |

147 | |

148 | template<typename T, typename Derived> |

149 | inline bool |

150 | vector_builder<T, Derived>::encoded_full_vector_p () const |

151 | { |

152 | return m_npatterns * m_nelts_per_pattern == m_full_nelts; |

153 | } |

154 | |

155 | /* Start building a vector that has FULL_NELTS elements. Initially |

156 | encode it using NPATTERNS patterns with NELTS_PER_PATTERN each. */ |

157 | |

158 | template<typename T, typename Derived> |

159 | void |

160 | vector_builder<T, Derived>::new_vector (unsigned int full_nelts, |

161 | unsigned int npatterns, |

162 | unsigned int nelts_per_pattern) |

163 | { |

164 | m_full_nelts = full_nelts; |

165 | m_npatterns = npatterns; |

166 | m_nelts_per_pattern = nelts_per_pattern; |

167 | this->reserve (encoded_nelts ()); |

168 | this->truncate (0); |

169 | } |

170 | |

171 | /* Return the value of vector element I, which might or might not be |

172 | encoded explicitly. */ |

173 | |

174 | template<typename T, typename Derived> |

175 | T |

176 | vector_builder<T, Derived>::elt (unsigned int i) const |

177 | { |

178 | /* This only makes sense if the encoding has been fully populated. */ |

179 | gcc_checking_assert (encoded_nelts () <= this->length ()); |

180 | |

181 | /* First handle elements that are already present in the underlying |

182 | vector, regardless of whether they're part of the encoding or not. */ |

183 | if (i < this->length ()) |

184 | return (*this)[i]; |

185 | |

186 | /* Identify the pattern that contains element I and work out the index of |

187 | the last encoded element for that pattern. */ |

188 | unsigned int pattern = i % m_npatterns; |

189 | unsigned int count = i / m_npatterns; |

190 | unsigned int final_i = encoded_nelts () - m_npatterns + pattern; |

191 | T final = (*this)[final_i]; |

192 | |

193 | /* If there are no steps, the final encoded value is the right one. */ |

194 | if (m_nelts_per_pattern <= 2) |

195 | return final; |

196 | |

197 | /* Otherwise work out the value from the last two encoded elements. */ |

198 | T prev = (*this)[final_i - m_npatterns]; |

199 | return derived ()->apply_step (final, count - 2, |

200 | derived ()->step (prev, final)); |

201 | } |

202 | |

203 | /* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each, |

204 | but without changing the underlying vector. */ |

205 | |

206 | template<typename T, typename Derived> |

207 | void |

208 | vector_builder<T, Derived>::reshape (unsigned int npatterns, |

209 | unsigned int nelts_per_pattern) |

210 | { |

211 | unsigned int old_encoded_nelts = encoded_nelts (); |

212 | unsigned int new_encoded_nelts = npatterns * nelts_per_pattern; |

213 | gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts); |

214 | unsigned int next = new_encoded_nelts - npatterns; |

215 | for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i) |

216 | { |

217 | derived ()->note_representative (&(*this)[next], (*this)[i]); |

218 | next += 1; |

219 | if (next == new_encoded_nelts) |

220 | next -= npatterns; |

221 | } |

222 | m_npatterns = npatterns; |

223 | m_nelts_per_pattern = nelts_per_pattern; |

224 | } |

225 | |

226 | /* Return true if elements [START, END) contain a repeating sequence of |

227 | STEP elements. */ |

228 | |

229 | template<typename T, typename Derived> |

230 | bool |

231 | vector_builder<T, Derived>::repeating_sequence_p (unsigned int start, |

232 | unsigned int end, |

233 | unsigned int step) |

234 | { |

235 | for (unsigned int i = start; i < end - step; ++i) |

236 | if (!derived ()->equal_p ((*this)[i], (*this)[i + step])) |

237 | return false; |

238 | return true; |

239 | } |

240 | |

241 | /* Return true if elements [START, END) contain STEP interleaved linear |

242 | series. */ |

243 | |

244 | template<typename T, typename Derived> |

245 | bool |

246 | vector_builder<T, Derived>::stepped_sequence_p (unsigned int start, |

247 | unsigned int end, |

248 | unsigned int step) |

249 | { |

250 | if (!derived ()->allow_steps_p ()) |

251 | return false; |

252 | |

253 | for (unsigned int i = start + step * 2; i < end; ++i) |

254 | { |

255 | T elt1 = (*this)[i - step * 2]; |

256 | T elt2 = (*this)[i - step]; |

257 | T elt3 = (*this)[i]; |

258 | |

259 | if (!derived ()->integral_p (elt1) |

260 | || !derived ()->integral_p (elt2) |

261 | || !derived ()->integral_p (elt3)) |

262 | return false; |

263 | |

264 | if (derived ()->step (elt1, elt2) != derived ()->step (elt2, elt3)) |

265 | return false; |

266 | |

267 | if (!derived ()->can_elide_p (elt3)) |

268 | return false; |

269 | } |

270 | return true; |

271 | } |

272 | |

273 | /* Try to change the number of encoded patterns to NPATTERNS, returning |

274 | true on success. */ |

275 | |

276 | template<typename T, typename Derived> |

277 | bool |

278 | vector_builder<T, Derived>::try_npatterns (unsigned int npatterns) |

279 | { |

280 | if (m_nelts_per_pattern == 1) |

281 | { |

282 | /* See whether NPATTERNS is valid with the current 1-element-per-pattern |

283 | encoding. */ |

284 | if (repeating_sequence_p (0, encoded_nelts (), npatterns)) |

285 | { |

286 | reshape (npatterns, 1); |

287 | return true; |

288 | } |

289 | |

290 | /* We can only increase the number of elements per pattern if all |

291 | elements are still encoded explicitly. */ |

292 | if (!encoded_full_vector_p ()) |

293 | return false; |

294 | } |

295 | |

296 | if (m_nelts_per_pattern <= 2) |

297 | { |

298 | /* See whether NPATTERNS is valid with a 2-element-per-pattern |

299 | encoding. */ |

300 | if (repeating_sequence_p (npatterns, encoded_nelts (), npatterns)) |

301 | { |

302 | reshape (npatterns, 2); |

303 | return true; |

304 | } |

305 | |

306 | /* We can only increase the number of elements per pattern if all |

307 | elements are still encoded explicitly. */ |

308 | if (!encoded_full_vector_p ()) |

309 | return false; |

310 | } |

311 | |

312 | if (m_nelts_per_pattern <= 3) |

313 | { |

314 | /* See whether we have NPATTERNS interleaved linear series, |

315 | giving a 3-element-per-pattern encoding. */ |

316 | if (stepped_sequence_p (npatterns, encoded_nelts (), npatterns)) |

317 | { |

318 | reshape (npatterns, 3); |

319 | return true; |

320 | } |

321 | return false; |

322 | } |

323 | |

324 | gcc_unreachable (); |

325 | } |

326 | |

327 | /* Replace the current encoding with the canonical form. */ |

328 | |

329 | template<typename T, typename Derived> |

330 | void |

331 | vector_builder<T, Derived>::finalize () |

332 | { |

333 | /* The encoding requires the same number of elements to come from each |

334 | pattern. */ |

335 | gcc_assert (m_full_nelts % m_npatterns == 0); |

336 | |

337 | /* Allow the caller to build more elements than necessary. For example, |

338 | it's often convenient to build a stepped vector from the natural |

339 | encoding of three elements even if the vector itself only has two. */ |

340 | if (m_full_nelts <= encoded_nelts ()) |

341 | { |

342 | m_npatterns = m_full_nelts; |

343 | m_nelts_per_pattern = 1; |

344 | } |

345 | |

346 | /* Try to whittle down the number of elements per pattern. That is: |

347 | |

348 | 1. If we have stepped patterns whose steps are all 0, reduce the |

349 | number of elements per pattern from 3 to 2. |

350 | |

351 | 2. If we have background fill values that are the same as the |

352 | foreground values, reduce the number of elements per pattern |

353 | from 2 to 1. */ |

354 | while (m_nelts_per_pattern > 1 |

355 | && repeating_sequence_p (encoded_nelts () - m_npatterns * 2, |

356 | encoded_nelts (), m_npatterns)) |

357 | /* The last two sequences of M_NPATTERNS elements are equal, |

358 | so remove the last one. */ |

359 | reshape (m_npatterns, m_nelts_per_pattern - 1); |

360 | |

361 | if (pow2p_hwi (m_npatterns)) |

362 | { |

363 | /* Try to halve the number of patterns while doing so gives a |

364 | valid pattern. This approach is linear in the number of |

365 | elements, whereas searcing from 1 up would be O(n*log(n)). |

366 | |

367 | Each halving step tries to keep the number of elements per pattern |

368 | the same. If that isn't possible, and if all elements are still |

369 | explicitly encoded, the halving step can instead increase the number |

370 | of elements per pattern. |

371 | |

372 | E.g. for: |

373 | |

374 | { 0, 2, 3, 4, 5, 6, 7, 8 } npatterns == 8 full_nelts == 8 |

375 | |

376 | we first realize that the second half of the sequence is not |

377 | equal to the first, so we cannot maintain 1 element per pattern |

378 | for npatterns == 4. Instead we halve the number of patterns |

379 | and double the number of elements per pattern, treating this |

380 | as a "foreground" { 0, 2, 3, 4 } against a "background" of |

381 | { 5, 6, 7, 8 | 5, 6, 7, 8 ... }: |

382 | |

383 | { 0, 2, 3, 4 | 5, 6, 7, 8 } npatterns == 4 |

384 | |

385 | Next we realize that this is *not* a foreround of { 0, 2 } |

386 | against a background of { 3, 4 | 3, 4 ... }, so the only |

387 | remaining option for reducing the number of patterns is |

388 | to use a foreground of { 0, 2 } against a stepped background |

389 | of { 1, 2 | 3, 4 | 5, 6 ... }. This is valid because we still |

390 | haven't elided any elements: |

391 | |

392 | { 0, 2 | 3, 4 | 5, 6 } npatterns == 2 |

393 | |

394 | This in turn can be reduced to a foreground of { 0 } against a |

395 | stepped background of { 1 | 2 | 3 ... }: |

396 | |

397 | { 0 | 2 | 3 } npatterns == 1 |

398 | |

399 | This last step would not have been possible for: |

400 | |

401 | { 0, 0 | 3, 4 | 5, 6 } npatterns == 2. */ |

402 | while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2)) |

403 | continue; |

404 | |

405 | /* Builders of arbitrary fixed-length vectors can use: |

406 | |

407 | new_vector (x, x, 1) |

408 | |

409 | so that every element is specified explicitly. Handle cases |

410 | that are actually wrapping series, like { 0, 1, 2, 3, 0, 1, 2, 3 } |

411 | would be for 2-bit elements. We'll have treated them as |

412 | duplicates in the loop above. */ |

413 | if (m_nelts_per_pattern == 1 |

414 | && this->length () >= m_full_nelts |

415 | && (m_npatterns & 3) == 0 |

416 | && stepped_sequence_p (m_npatterns / 4, m_full_nelts, |

417 | m_npatterns / 4)) |

418 | { |

419 | reshape (m_npatterns / 4, 3); |

420 | while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2)) |

421 | continue; |

422 | } |

423 | } |

424 | else |

425 | /* For the non-power-of-2 case, do a simple search up from 1. */ |

426 | for (unsigned int i = 1; i <= m_npatterns / 2; ++i) |

427 | if (m_npatterns % i == 0 && try_npatterns (i)) |

428 | break; |

429 | } |

430 | |

431 | #endif |

432 |

Warning: That file was not part of the compilation database. It may have many parsing errors.