1 | //===-- llvm/Analysis/DependenceAnalysis.h -------------------- -*- C++ -*-===// |
---|---|

2 | // |

3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |

4 | // See https://llvm.org/LICENSE.txt for license information. |

5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |

6 | // |

7 | //===----------------------------------------------------------------------===// |

8 | // |

9 | // DependenceAnalysis is an LLVM pass that analyses dependences between memory |

10 | // accesses. Currently, it is an implementation of the approach described in |

11 | // |

12 | // Practical Dependence Testing |

13 | // Goff, Kennedy, Tseng |

14 | // PLDI 1991 |

15 | // |

16 | // There's a single entry point that analyzes the dependence between a pair |

17 | // of memory references in a function, returning either NULL, for no dependence, |

18 | // or a more-or-less detailed description of the dependence between them. |

19 | // |

20 | // This pass exists to support the DependenceGraph pass. There are two separate |

21 | // passes because there's a useful separation of concerns. A dependence exists |

22 | // if two conditions are met: |

23 | // |

24 | // 1) Two instructions reference the same memory location, and |

25 | // 2) There is a flow of control leading from one instruction to the other. |

26 | // |

27 | // DependenceAnalysis attacks the first condition; DependenceGraph will attack |

28 | // the second (it's not yet ready). |

29 | // |

30 | // Please note that this is work in progress and the interface is subject to |

31 | // change. |

32 | // |

33 | // Plausible changes: |

34 | // Return a set of more precise dependences instead of just one dependence |

35 | // summarizing all. |

36 | // |

37 | //===----------------------------------------------------------------------===// |

38 | |

39 | #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H |

40 | #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H |

41 | |

42 | #include "llvm/ADT/SmallBitVector.h" |

43 | #include "llvm/IR/Instructions.h" |

44 | #include "llvm/IR/PassManager.h" |

45 | #include "llvm/Pass.h" |

46 | |

47 | namespace llvm { |

48 | class AAResults; |

49 | template <typename T> class ArrayRef; |

50 | class Loop; |

51 | class LoopInfo; |

52 | class ScalarEvolution; |

53 | class SCEV; |

54 | class SCEVConstant; |

55 | class raw_ostream; |

56 | |

57 | /// Dependence - This class represents a dependence between two memory |

58 | /// memory references in a function. It contains minimal information and |

59 | /// is used in the very common situation where the compiler is unable to |

60 | /// determine anything beyond the existence of a dependence; that is, it |

61 | /// represents a confused dependence (see also FullDependence). In most |

62 | /// cases (for output, flow, and anti dependences), the dependence implies |

63 | /// an ordering, where the source must precede the destination; in contrast, |

64 | /// input dependences are unordered. |

65 | /// |

66 | /// When a dependence graph is built, each Dependence will be a member of |

67 | /// the set of predecessor edges for its destination instruction and a set |

68 | /// if successor edges for its source instruction. These sets are represented |

69 | /// as singly-linked lists, with the "next" fields stored in the dependence |

70 | /// itelf. |

71 | class Dependence { |

72 | protected: |

73 | Dependence(Dependence &&) = default; |

74 | Dependence &operator=(Dependence &&) = default; |

75 | |

76 | public: |

77 | Dependence(Instruction *Source, Instruction *Destination) |

78 | : Src(Source), Dst(Destination) {} |

79 | virtual ~Dependence() = default; |

80 | |

81 | /// Dependence::DVEntry - Each level in the distance/direction vector |

82 | /// has a direction (or perhaps a union of several directions), and |

83 | /// perhaps a distance. |

84 | struct DVEntry { |

85 | enum { NONE = 0, |

86 | LT = 1, |

87 | EQ = 2, |

88 | LE = 3, |

89 | GT = 4, |

90 | NE = 5, |

91 | GE = 6, |

92 | ALL = 7 }; |

93 | unsigned char Direction : 3; // Init to ALL, then refine. |

94 | bool Scalar : 1; // Init to true. |

95 | bool PeelFirst : 1; // Peeling the first iteration will break dependence. |

96 | bool PeelLast : 1; // Peeling the last iteration will break the dependence. |

97 | bool Splitable : 1; // Splitting the loop will break dependence. |

98 | const SCEV *Distance = nullptr; // NULL implies no distance available. |

99 | DVEntry() |

100 | : Direction(ALL), Scalar(true), PeelFirst(false), PeelLast(false), |

101 | Splitable(false) {} |

102 | }; |

103 | |

104 | /// getSrc - Returns the source instruction for this dependence. |

105 | /// |

106 | Instruction *getSrc() const { return Src; } |

107 | |

108 | /// getDst - Returns the destination instruction for this dependence. |

109 | /// |

110 | Instruction *getDst() const { return Dst; } |

111 | |

112 | /// isInput - Returns true if this is an input dependence. |

113 | /// |

114 | bool isInput() const; |

115 | |

116 | /// isOutput - Returns true if this is an output dependence. |

117 | /// |

118 | bool isOutput() const; |

119 | |

120 | /// isFlow - Returns true if this is a flow (aka true) dependence. |

121 | /// |

122 | bool isFlow() const; |

123 | |

124 | /// isAnti - Returns true if this is an anti dependence. |

125 | /// |

126 | bool isAnti() const; |

127 | |

128 | /// isOrdered - Returns true if dependence is Output, Flow, or Anti |

129 | /// |

130 | bool isOrdered() const { return isOutput() || isFlow() || isAnti(); } |

131 | |

132 | /// isUnordered - Returns true if dependence is Input |

133 | /// |

134 | bool isUnordered() const { return isInput(); } |

135 | |

136 | /// isLoopIndependent - Returns true if this is a loop-independent |

137 | /// dependence. |

138 | virtual bool isLoopIndependent() const { return true; } |

139 | |

140 | /// isConfused - Returns true if this dependence is confused |

141 | /// (the compiler understands nothing and makes worst-case |

142 | /// assumptions). |

143 | virtual bool isConfused() const { return true; } |

144 | |

145 | /// isConsistent - Returns true if this dependence is consistent |

146 | /// (occurs every time the source and destination are executed). |

147 | virtual bool isConsistent() const { return false; } |

148 | |

149 | /// getLevels - Returns the number of common loops surrounding the |

150 | /// source and destination of the dependence. |

151 | virtual unsigned getLevels() const { return 0; } |

152 | |

153 | /// getDirection - Returns the direction associated with a particular |

154 | /// level. |

155 | virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; } |

156 | |

157 | /// getDistance - Returns the distance (or NULL) associated with a |

158 | /// particular level. |

159 | virtual const SCEV *getDistance(unsigned Level) const { return nullptr; } |

160 | |

161 | /// Check if the direction vector is negative. A negative direction |

162 | /// vector means Src and Dst are reversed in the actual program. |

163 | virtual bool isDirectionNegative() const { return false; } |

164 | |

165 | /// If the direction vector is negative, normalize the direction |

166 | /// vector to make it non-negative. Normalization is done by reversing |

167 | /// Src and Dst, plus reversing the dependence directions and distances |

168 | /// in the vector. |

169 | virtual bool normalize(ScalarEvolution *SE) { return false; } |

170 | |

171 | /// isPeelFirst - Returns true if peeling the first iteration from |

172 | /// this loop will break this dependence. |

173 | virtual bool isPeelFirst(unsigned Level) const { return false; } |

174 | |

175 | /// isPeelLast - Returns true if peeling the last iteration from |

176 | /// this loop will break this dependence. |

177 | virtual bool isPeelLast(unsigned Level) const { return false; } |

178 | |

179 | /// isSplitable - Returns true if splitting this loop will break |

180 | /// the dependence. |

181 | virtual bool isSplitable(unsigned Level) const { return false; } |

182 | |

183 | /// isScalar - Returns true if a particular level is scalar; that is, |

184 | /// if no subscript in the source or destination mention the induction |

185 | /// variable associated with the loop at this level. |

186 | virtual bool isScalar(unsigned Level) const; |

187 | |

188 | /// getNextPredecessor - Returns the value of the NextPredecessor |

189 | /// field. |

190 | const Dependence *getNextPredecessor() const { return NextPredecessor; } |

191 | |

192 | /// getNextSuccessor - Returns the value of the NextSuccessor |

193 | /// field. |

194 | const Dependence *getNextSuccessor() const { return NextSuccessor; } |

195 | |

196 | /// setNextPredecessor - Sets the value of the NextPredecessor |

197 | /// field. |

198 | void setNextPredecessor(const Dependence *pred) { NextPredecessor = pred; } |

199 | |

200 | /// setNextSuccessor - Sets the value of the NextSuccessor |

201 | /// field. |

202 | void setNextSuccessor(const Dependence *succ) { NextSuccessor = succ; } |

203 | |

204 | /// dump - For debugging purposes, dumps a dependence to OS. |

205 | /// |

206 | void dump(raw_ostream &OS) const; |

207 | |

208 | protected: |

209 | Instruction *Src, *Dst; |

210 | |

211 | private: |

212 | const Dependence *NextPredecessor = nullptr, *NextSuccessor = nullptr; |

213 | friend class DependenceInfo; |

214 | }; |

215 | |

216 | /// FullDependence - This class represents a dependence between two memory |

217 | /// references in a function. It contains detailed information about the |

218 | /// dependence (direction vectors, etc.) and is used when the compiler is |

219 | /// able to accurately analyze the interaction of the references; that is, |

220 | /// it is not a confused dependence (see Dependence). In most cases |

221 | /// (for output, flow, and anti dependences), the dependence implies an |

222 | /// ordering, where the source must precede the destination; in contrast, |

223 | /// input dependences are unordered. |

224 | class FullDependence final : public Dependence { |

225 | public: |

226 | FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, |

227 | unsigned Levels); |

228 | |

229 | /// isLoopIndependent - Returns true if this is a loop-independent |

230 | /// dependence. |

231 | bool isLoopIndependent() const override { return LoopIndependent; } |

232 | |

233 | /// isConfused - Returns true if this dependence is confused |

234 | /// (the compiler understands nothing and makes worst-case |

235 | /// assumptions). |

236 | bool isConfused() const override { return false; } |

237 | |

238 | /// isConsistent - Returns true if this dependence is consistent |

239 | /// (occurs every time the source and destination are executed). |

240 | bool isConsistent() const override { return Consistent; } |

241 | |

242 | /// getLevels - Returns the number of common loops surrounding the |

243 | /// source and destination of the dependence. |

244 | unsigned getLevels() const override { return Levels; } |

245 | |

246 | /// getDirection - Returns the direction associated with a particular |

247 | /// level. |

248 | unsigned getDirection(unsigned Level) const override; |

249 | |

250 | /// getDistance - Returns the distance (or NULL) associated with a |

251 | /// particular level. |

252 | const SCEV *getDistance(unsigned Level) const override; |

253 | |

254 | /// Check if the direction vector is negative. A negative direction |

255 | /// vector means Src and Dst are reversed in the actual program. |

256 | bool isDirectionNegative() const override; |

257 | |

258 | /// If the direction vector is negative, normalize the direction |

259 | /// vector to make it non-negative. Normalization is done by reversing |

260 | /// Src and Dst, plus reversing the dependence directions and distances |

261 | /// in the vector. |

262 | bool normalize(ScalarEvolution *SE) override; |

263 | |

264 | /// isPeelFirst - Returns true if peeling the first iteration from |

265 | /// this loop will break this dependence. |

266 | bool isPeelFirst(unsigned Level) const override; |

267 | |

268 | /// isPeelLast - Returns true if peeling the last iteration from |

269 | /// this loop will break this dependence. |

270 | bool isPeelLast(unsigned Level) const override; |

271 | |

272 | /// isSplitable - Returns true if splitting the loop will break |

273 | /// the dependence. |

274 | bool isSplitable(unsigned Level) const override; |

275 | |

276 | /// isScalar - Returns true if a particular level is scalar; that is, |

277 | /// if no subscript in the source or destination mention the induction |

278 | /// variable associated with the loop at this level. |

279 | bool isScalar(unsigned Level) const override; |

280 | |

281 | private: |

282 | unsigned short Levels; |

283 | bool LoopIndependent; |

284 | bool Consistent; // Init to true, then refine. |

285 | std::unique_ptr<DVEntry[]> DV; |

286 | friend class DependenceInfo; |

287 | }; |

288 | |

289 | /// DependenceInfo - This class is the main dependence-analysis driver. |

290 | /// |

291 | class DependenceInfo { |

292 | public: |

293 | DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, |

294 | LoopInfo *LI) |

295 | : AA(AA), SE(SE), LI(LI), F(F) {} |

296 | |

297 | /// Handle transitive invalidation when the cached analysis results go away. |

298 | bool invalidate(Function &F, const PreservedAnalyses &PA, |

299 | FunctionAnalysisManager::Invalidator &Inv); |

300 | |

301 | /// depends - Tests for a dependence between the Src and Dst instructions. |

302 | /// Returns NULL if no dependence; otherwise, returns a Dependence (or a |

303 | /// FullDependence) with as much information as can be gleaned. |

304 | /// The flag PossiblyLoopIndependent should be set by the caller |

305 | /// if it appears that control flow can reach from Src to Dst |

306 | /// without traversing a loop back edge. |

307 | std::unique_ptr<Dependence> depends(Instruction *Src, |

308 | Instruction *Dst, |

309 | bool PossiblyLoopIndependent); |

310 | |

311 | /// getSplitIteration - Give a dependence that's splittable at some |

312 | /// particular level, return the iteration that should be used to split |

313 | /// the loop. |

314 | /// |

315 | /// Generally, the dependence analyzer will be used to build |

316 | /// a dependence graph for a function (basically a map from instructions |

317 | /// to dependences). Looking for cycles in the graph shows us loops |

318 | /// that cannot be trivially vectorized/parallelized. |

319 | /// |

320 | /// We can try to improve the situation by examining all the dependences |

321 | /// that make up the cycle, looking for ones we can break. |

322 | /// Sometimes, peeling the first or last iteration of a loop will break |

323 | /// dependences, and there are flags for those possibilities. |

324 | /// Sometimes, splitting a loop at some other iteration will do the trick, |

325 | /// and we've got a flag for that case. Rather than waste the space to |

326 | /// record the exact iteration (since we rarely know), we provide |

327 | /// a method that calculates the iteration. It's a drag that it must work |

328 | /// from scratch, but wonderful in that it's possible. |

329 | /// |

330 | /// Here's an example: |

331 | /// |

332 | /// for (i = 0; i < 10; i++) |

333 | /// A[i] = ... |

334 | /// ... = A[11 - i] |

335 | /// |

336 | /// There's a loop-carried flow dependence from the store to the load, |

337 | /// found by the weak-crossing SIV test. The dependence will have a flag, |

338 | /// indicating that the dependence can be broken by splitting the loop. |

339 | /// Calling getSplitIteration will return 5. |

340 | /// Splitting the loop breaks the dependence, like so: |

341 | /// |

342 | /// for (i = 0; i <= 5; i++) |

343 | /// A[i] = ... |

344 | /// ... = A[11 - i] |

345 | /// for (i = 6; i < 10; i++) |

346 | /// A[i] = ... |

347 | /// ... = A[11 - i] |

348 | /// |

349 | /// breaks the dependence and allows us to vectorize/parallelize |

350 | /// both loops. |

351 | const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level); |

352 | |

353 | Function *getFunction() const { return F; } |

354 | |

355 | private: |

356 | AAResults *AA; |

357 | ScalarEvolution *SE; |

358 | LoopInfo *LI; |

359 | Function *F; |

360 | |

361 | /// Subscript - This private struct represents a pair of subscripts from |

362 | /// a pair of potentially multi-dimensional array references. We use a |

363 | /// vector of them to guide subscript partitioning. |

364 | struct Subscript { |

365 | const SCEV *Src; |

366 | const SCEV *Dst; |

367 | enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification; |

368 | SmallBitVector Loops; |

369 | SmallBitVector GroupLoops; |

370 | SmallBitVector Group; |

371 | }; |

372 | |

373 | struct CoefficientInfo { |

374 | const SCEV *Coeff; |

375 | const SCEV *PosPart; |

376 | const SCEV *NegPart; |

377 | const SCEV *Iterations; |

378 | }; |

379 | |

380 | struct BoundInfo { |

381 | const SCEV *Iterations; |

382 | const SCEV *Upper[8]; |

383 | const SCEV *Lower[8]; |

384 | unsigned char Direction; |

385 | unsigned char DirSet; |

386 | }; |

387 | |

388 | /// Constraint - This private class represents a constraint, as defined |

389 | /// in the paper |

390 | /// |

391 | /// Practical Dependence Testing |

392 | /// Goff, Kennedy, Tseng |

393 | /// PLDI 1991 |

394 | /// |

395 | /// There are 5 kinds of constraint, in a hierarchy. |

396 | /// 1) Any - indicates no constraint, any dependence is possible. |

397 | /// 2) Line - A line ax + by = c, where a, b, and c are parameters, |

398 | /// representing the dependence equation. |

399 | /// 3) Distance - The value d of the dependence distance; |

400 | /// 4) Point - A point <x, y> representing the dependence from |

401 | /// iteration x to iteration y. |

402 | /// 5) Empty - No dependence is possible. |

403 | class Constraint { |

404 | private: |

405 | enum ConstraintKind { Empty, Point, Distance, Line, Any } Kind; |

406 | ScalarEvolution *SE; |

407 | const SCEV *A; |

408 | const SCEV *B; |

409 | const SCEV *C; |

410 | const Loop *AssociatedLoop; |

411 | |

412 | public: |

413 | /// isEmpty - Return true if the constraint is of kind Empty. |

414 | bool isEmpty() const { return Kind == Empty; } |

415 | |

416 | /// isPoint - Return true if the constraint is of kind Point. |

417 | bool isPoint() const { return Kind == Point; } |

418 | |

419 | /// isDistance - Return true if the constraint is of kind Distance. |

420 | bool isDistance() const { return Kind == Distance; } |

421 | |

422 | /// isLine - Return true if the constraint is of kind Line. |

423 | /// Since Distance's can also be represented as Lines, we also return |

424 | /// true if the constraint is of kind Distance. |

425 | bool isLine() const { return Kind == Line || Kind == Distance; } |

426 | |

427 | /// isAny - Return true if the constraint is of kind Any; |

428 | bool isAny() const { return Kind == Any; } |

429 | |

430 | /// getX - If constraint is a point <X, Y>, returns X. |

431 | /// Otherwise assert. |

432 | const SCEV *getX() const; |

433 | |

434 | /// getY - If constraint is a point <X, Y>, returns Y. |

435 | /// Otherwise assert. |

436 | const SCEV *getY() const; |

437 | |

438 | /// getA - If constraint is a line AX + BY = C, returns A. |

439 | /// Otherwise assert. |

440 | const SCEV *getA() const; |

441 | |

442 | /// getB - If constraint is a line AX + BY = C, returns B. |

443 | /// Otherwise assert. |

444 | const SCEV *getB() const; |

445 | |

446 | /// getC - If constraint is a line AX + BY = C, returns C. |

447 | /// Otherwise assert. |

448 | const SCEV *getC() const; |

449 | |

450 | /// getD - If constraint is a distance, returns D. |

451 | /// Otherwise assert. |

452 | const SCEV *getD() const; |

453 | |

454 | /// getAssociatedLoop - Returns the loop associated with this constraint. |

455 | const Loop *getAssociatedLoop() const; |

456 | |

457 | /// setPoint - Change a constraint to Point. |

458 | void setPoint(const SCEV *X, const SCEV *Y, const Loop *CurrentLoop); |

459 | |

460 | /// setLine - Change a constraint to Line. |

461 | void setLine(const SCEV *A, const SCEV *B, |

462 | const SCEV *C, const Loop *CurrentLoop); |

463 | |

464 | /// setDistance - Change a constraint to Distance. |

465 | void setDistance(const SCEV *D, const Loop *CurrentLoop); |

466 | |

467 | /// setEmpty - Change a constraint to Empty. |

468 | void setEmpty(); |

469 | |

470 | /// setAny - Change a constraint to Any. |

471 | void setAny(ScalarEvolution *SE); |

472 | |

473 | /// dump - For debugging purposes. Dumps the constraint |

474 | /// out to OS. |

475 | void dump(raw_ostream &OS) const; |

476 | }; |

477 | |

478 | /// establishNestingLevels - Examines the loop nesting of the Src and Dst |

479 | /// instructions and establishes their shared loops. Sets the variables |

480 | /// CommonLevels, SrcLevels, and MaxLevels. |

481 | /// The source and destination instructions needn't be contained in the same |

482 | /// loop. The routine establishNestingLevels finds the level of most deeply |

483 | /// nested loop that contains them both, CommonLevels. An instruction that's |

484 | /// not contained in a loop is at level = 0. MaxLevels is equal to the level |

485 | /// of the source plus the level of the destination, minus CommonLevels. |

486 | /// This lets us allocate vectors MaxLevels in length, with room for every |

487 | /// distinct loop referenced in both the source and destination subscripts. |

488 | /// The variable SrcLevels is the nesting depth of the source instruction. |

489 | /// It's used to help calculate distinct loops referenced by the destination. |

490 | /// Here's the map from loops to levels: |

491 | /// 0 - unused |

492 | /// 1 - outermost common loop |

493 | /// ... - other common loops |

494 | /// CommonLevels - innermost common loop |

495 | /// ... - loops containing Src but not Dst |

496 | /// SrcLevels - innermost loop containing Src but not Dst |

497 | /// ... - loops containing Dst but not Src |

498 | /// MaxLevels - innermost loop containing Dst but not Src |

499 | /// Consider the follow code fragment: |

500 | /// for (a = ...) { |

501 | /// for (b = ...) { |

502 | /// for (c = ...) { |

503 | /// for (d = ...) { |

504 | /// A[] = ...; |

505 | /// } |

506 | /// } |

507 | /// for (e = ...) { |

508 | /// for (f = ...) { |

509 | /// for (g = ...) { |

510 | /// ... = A[]; |

511 | /// } |

512 | /// } |

513 | /// } |

514 | /// } |

515 | /// } |

516 | /// If we're looking at the possibility of a dependence between the store |

517 | /// to A (the Src) and the load from A (the Dst), we'll note that they |

518 | /// have 2 loops in common, so CommonLevels will equal 2 and the direction |

519 | /// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. |

520 | /// A map from loop names to level indices would look like |

521 | /// a - 1 |

522 | /// b - 2 = CommonLevels |

523 | /// c - 3 |

524 | /// d - 4 = SrcLevels |

525 | /// e - 5 |

526 | /// f - 6 |

527 | /// g - 7 = MaxLevels |

528 | void establishNestingLevels(const Instruction *Src, |

529 | const Instruction *Dst); |

530 | |

531 | unsigned CommonLevels, SrcLevels, MaxLevels; |

532 | |

533 | /// mapSrcLoop - Given one of the loops containing the source, return |

534 | /// its level index in our numbering scheme. |

535 | unsigned mapSrcLoop(const Loop *SrcLoop) const; |

536 | |

537 | /// mapDstLoop - Given one of the loops containing the destination, |

538 | /// return its level index in our numbering scheme. |

539 | unsigned mapDstLoop(const Loop *DstLoop) const; |

540 | |

541 | /// isLoopInvariant - Returns true if Expression is loop invariant |

542 | /// in LoopNest. |

543 | bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const; |

544 | |

545 | /// Makes sure all subscript pairs share the same integer type by |

546 | /// sign-extending as necessary. |

547 | /// Sign-extending a subscript is safe because getelementptr assumes the |

548 | /// array subscripts are signed. |

549 | void unifySubscriptType(ArrayRef<Subscript *> Pairs); |

550 | |

551 | /// removeMatchingExtensions - Examines a subscript pair. |

552 | /// If the source and destination are identically sign (or zero) |

553 | /// extended, it strips off the extension in an effort to |

554 | /// simplify the actual analysis. |

555 | void removeMatchingExtensions(Subscript *Pair); |

556 | |

557 | /// collectCommonLoops - Finds the set of loops from the LoopNest that |

558 | /// have a level <= CommonLevels and are referred to by the SCEV Expression. |

559 | void collectCommonLoops(const SCEV *Expression, |

560 | const Loop *LoopNest, |

561 | SmallBitVector &Loops) const; |

562 | |

563 | /// checkSrcSubscript - Examines the SCEV Src, returning true iff it's |

564 | /// linear. Collect the set of loops mentioned by Src. |

565 | bool checkSrcSubscript(const SCEV *Src, |

566 | const Loop *LoopNest, |

567 | SmallBitVector &Loops); |

568 | |

569 | /// checkDstSubscript - Examines the SCEV Dst, returning true iff it's |

570 | /// linear. Collect the set of loops mentioned by Dst. |

571 | bool checkDstSubscript(const SCEV *Dst, |

572 | const Loop *LoopNest, |

573 | SmallBitVector &Loops); |

574 | |

575 | /// isKnownPredicate - Compare X and Y using the predicate Pred. |

576 | /// Basically a wrapper for SCEV::isKnownPredicate, |

577 | /// but tries harder, especially in the presence of sign and zero |

578 | /// extensions and symbolics. |

579 | bool isKnownPredicate(ICmpInst::Predicate Pred, |

580 | const SCEV *X, |

581 | const SCEV *Y) const; |

582 | |

583 | /// isKnownLessThan - Compare to see if S is less than Size |

584 | /// Another wrapper for isKnownNegative(S - max(Size, 1)) with some extra |

585 | /// checking if S is an AddRec and we can prove lessthan using the loop |

586 | /// bounds. |

587 | bool isKnownLessThan(const SCEV *S, const SCEV *Size) const; |

588 | |

589 | /// isKnownNonNegative - Compare to see if S is known not to be negative |

590 | /// Uses the fact that S comes from Ptr, which may be an inbound GEP, |

591 | /// Proving there is no wrapping going on. |

592 | bool isKnownNonNegative(const SCEV *S, const Value *Ptr) const; |

593 | |

594 | /// collectUpperBound - All subscripts are the same type (on my machine, |

595 | /// an i64). The loop bound may be a smaller type. collectUpperBound |

596 | /// find the bound, if available, and zero extends it to the Type T. |

597 | /// (I zero extend since the bound should always be >= 0.) |

598 | /// If no upper bound is available, return NULL. |

599 | const SCEV *collectUpperBound(const Loop *l, Type *T) const; |

600 | |

601 | /// collectConstantUpperBound - Calls collectUpperBound(), then |

602 | /// attempts to cast it to SCEVConstant. If the cast fails, |

603 | /// returns NULL. |

604 | const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const; |

605 | |

606 | /// classifyPair - Examines the subscript pair (the Src and Dst SCEVs) |

607 | /// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. |

608 | /// Collects the associated loops in a set. |

609 | Subscript::ClassificationKind classifyPair(const SCEV *Src, |

610 | const Loop *SrcLoopNest, |

611 | const SCEV *Dst, |

612 | const Loop *DstLoopNest, |

613 | SmallBitVector &Loops); |

614 | |

615 | /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence. |

616 | /// Returns true if any possible dependence is disproved. |

617 | /// If there might be a dependence, returns false. |

618 | /// If the dependence isn't proven to exist, |

619 | /// marks the Result as inconsistent. |

620 | bool testZIV(const SCEV *Src, |

621 | const SCEV *Dst, |

622 | FullDependence &Result) const; |

623 | |

624 | /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence. |

625 | /// Things of the form [c1 + a1*i] and [c2 + a2*j], where |

626 | /// i and j are induction variables, c1 and c2 are loop invariant, |

627 | /// and a1 and a2 are constant. |

628 | /// Returns true if any possible dependence is disproved. |

629 | /// If there might be a dependence, returns false. |

630 | /// Sets appropriate direction vector entry and, when possible, |

631 | /// the distance vector entry. |

632 | /// If the dependence isn't proven to exist, |

633 | /// marks the Result as inconsistent. |

634 | bool testSIV(const SCEV *Src, |

635 | const SCEV *Dst, |

636 | unsigned &Level, |

637 | FullDependence &Result, |

638 | Constraint &NewConstraint, |

639 | const SCEV *&SplitIter) const; |

640 | |

641 | /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence. |

642 | /// Things of the form [c1 + a1*i] and [c2 + a2*j] |

643 | /// where i and j are induction variables, c1 and c2 are loop invariant, |

644 | /// and a1 and a2 are constant. |

645 | /// With minor algebra, this test can also be used for things like |

646 | /// [c1 + a1*i + a2*j][c2]. |

647 | /// Returns true if any possible dependence is disproved. |

648 | /// If there might be a dependence, returns false. |

649 | /// Marks the Result as inconsistent. |

650 | bool testRDIV(const SCEV *Src, |

651 | const SCEV *Dst, |

652 | FullDependence &Result) const; |

653 | |

654 | /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence. |

655 | /// Returns true if dependence disproved. |

656 | /// Can sometimes refine direction vectors. |

657 | bool testMIV(const SCEV *Src, |

658 | const SCEV *Dst, |

659 | const SmallBitVector &Loops, |

660 | FullDependence &Result) const; |

661 | |

662 | /// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) |

663 | /// for dependence. |

664 | /// Things of the form [c1 + a*i] and [c2 + a*i], |

665 | /// where i is an induction variable, c1 and c2 are loop invariant, |

666 | /// and a is a constant |

667 | /// Returns true if any possible dependence is disproved. |

668 | /// If there might be a dependence, returns false. |

669 | /// Sets appropriate direction and distance. |

670 | bool strongSIVtest(const SCEV *Coeff, |

671 | const SCEV *SrcConst, |

672 | const SCEV *DstConst, |

673 | const Loop *CurrentLoop, |

674 | unsigned Level, |

675 | FullDependence &Result, |

676 | Constraint &NewConstraint) const; |

677 | |

678 | /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair |

679 | /// (Src and Dst) for dependence. |

680 | /// Things of the form [c1 + a*i] and [c2 - a*i], |

681 | /// where i is an induction variable, c1 and c2 are loop invariant, |

682 | /// and a is a constant. |

683 | /// Returns true if any possible dependence is disproved. |

684 | /// If there might be a dependence, returns false. |

685 | /// Sets appropriate direction entry. |

686 | /// Set consistent to false. |

687 | /// Marks the dependence as splitable. |

688 | bool weakCrossingSIVtest(const SCEV *SrcCoeff, |

689 | const SCEV *SrcConst, |

690 | const SCEV *DstConst, |

691 | const Loop *CurrentLoop, |

692 | unsigned Level, |

693 | FullDependence &Result, |

694 | Constraint &NewConstraint, |

695 | const SCEV *&SplitIter) const; |

696 | |

697 | /// ExactSIVtest - Tests the SIV subscript pair |

698 | /// (Src and Dst) for dependence. |

699 | /// Things of the form [c1 + a1*i] and [c2 + a2*i], |

700 | /// where i is an induction variable, c1 and c2 are loop invariant, |

701 | /// and a1 and a2 are constant. |

702 | /// Returns true if any possible dependence is disproved. |

703 | /// If there might be a dependence, returns false. |

704 | /// Sets appropriate direction entry. |

705 | /// Set consistent to false. |

706 | bool exactSIVtest(const SCEV *SrcCoeff, |

707 | const SCEV *DstCoeff, |

708 | const SCEV *SrcConst, |

709 | const SCEV *DstConst, |

710 | const Loop *CurrentLoop, |

711 | unsigned Level, |

712 | FullDependence &Result, |

713 | Constraint &NewConstraint) const; |

714 | |

715 | /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair |

716 | /// (Src and Dst) for dependence. |

717 | /// Things of the form [c1] and [c2 + a*i], |

718 | /// where i is an induction variable, c1 and c2 are loop invariant, |

719 | /// and a is a constant. See also weakZeroDstSIVtest. |

720 | /// Returns true if any possible dependence is disproved. |

721 | /// If there might be a dependence, returns false. |

722 | /// Sets appropriate direction entry. |

723 | /// Set consistent to false. |

724 | /// If loop peeling will break the dependence, mark appropriately. |

725 | bool weakZeroSrcSIVtest(const SCEV *DstCoeff, |

726 | const SCEV *SrcConst, |

727 | const SCEV *DstConst, |

728 | const Loop *CurrentLoop, |

729 | unsigned Level, |

730 | FullDependence &Result, |

731 | Constraint &NewConstraint) const; |

732 | |

733 | /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair |

734 | /// (Src and Dst) for dependence. |

735 | /// Things of the form [c1 + a*i] and [c2], |

736 | /// where i is an induction variable, c1 and c2 are loop invariant, |

737 | /// and a is a constant. See also weakZeroSrcSIVtest. |

738 | /// Returns true if any possible dependence is disproved. |

739 | /// If there might be a dependence, returns false. |

740 | /// Sets appropriate direction entry. |

741 | /// Set consistent to false. |

742 | /// If loop peeling will break the dependence, mark appropriately. |

743 | bool weakZeroDstSIVtest(const SCEV *SrcCoeff, |

744 | const SCEV *SrcConst, |

745 | const SCEV *DstConst, |

746 | const Loop *CurrentLoop, |

747 | unsigned Level, |

748 | FullDependence &Result, |

749 | Constraint &NewConstraint) const; |

750 | |

751 | /// exactRDIVtest - Tests the RDIV subscript pair for dependence. |

752 | /// Things of the form [c1 + a*i] and [c2 + b*j], |

753 | /// where i and j are induction variable, c1 and c2 are loop invariant, |

754 | /// and a and b are constants. |

755 | /// Returns true if any possible dependence is disproved. |

756 | /// Marks the result as inconsistent. |

757 | /// Works in some cases that symbolicRDIVtest doesn't, |

758 | /// and vice versa. |

759 | bool exactRDIVtest(const SCEV *SrcCoeff, |

760 | const SCEV *DstCoeff, |

761 | const SCEV *SrcConst, |

762 | const SCEV *DstConst, |

763 | const Loop *SrcLoop, |

764 | const Loop *DstLoop, |

765 | FullDependence &Result) const; |

766 | |

767 | /// symbolicRDIVtest - Tests the RDIV subscript pair for dependence. |

768 | /// Things of the form [c1 + a*i] and [c2 + b*j], |

769 | /// where i and j are induction variable, c1 and c2 are loop invariant, |

770 | /// and a and b are constants. |

771 | /// Returns true if any possible dependence is disproved. |

772 | /// Marks the result as inconsistent. |

773 | /// Works in some cases that exactRDIVtest doesn't, |

774 | /// and vice versa. Can also be used as a backup for |

775 | /// ordinary SIV tests. |

776 | bool symbolicRDIVtest(const SCEV *SrcCoeff, |

777 | const SCEV *DstCoeff, |

778 | const SCEV *SrcConst, |

779 | const SCEV *DstConst, |

780 | const Loop *SrcLoop, |

781 | const Loop *DstLoop) const; |

782 | |

783 | /// gcdMIVtest - Tests an MIV subscript pair for dependence. |

784 | /// Returns true if any possible dependence is disproved. |

785 | /// Marks the result as inconsistent. |

786 | /// Can sometimes disprove the equal direction for 1 or more loops. |

787 | // Can handle some symbolics that even the SIV tests don't get, |

788 | /// so we use it as a backup for everything. |

789 | bool gcdMIVtest(const SCEV *Src, |

790 | const SCEV *Dst, |

791 | FullDependence &Result) const; |

792 | |

793 | /// banerjeeMIVtest - Tests an MIV subscript pair for dependence. |

794 | /// Returns true if any possible dependence is disproved. |

795 | /// Marks the result as inconsistent. |

796 | /// Computes directions. |

797 | bool banerjeeMIVtest(const SCEV *Src, |

798 | const SCEV *Dst, |

799 | const SmallBitVector &Loops, |

800 | FullDependence &Result) const; |

801 | |

802 | /// collectCoefficientInfo - Walks through the subscript, |

803 | /// collecting each coefficient, the associated loop bounds, |

804 | /// and recording its positive and negative parts for later use. |

805 | CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, |

806 | bool SrcFlag, |

807 | const SCEV *&Constant) const; |

808 | |

809 | /// getPositivePart - X^+ = max(X, 0). |

810 | /// |

811 | const SCEV *getPositivePart(const SCEV *X) const; |

812 | |

813 | /// getNegativePart - X^- = min(X, 0). |

814 | /// |

815 | const SCEV *getNegativePart(const SCEV *X) const; |

816 | |

817 | /// getLowerBound - Looks through all the bounds info and |

818 | /// computes the lower bound given the current direction settings |

819 | /// at each level. |

820 | const SCEV *getLowerBound(BoundInfo *Bound) const; |

821 | |

822 | /// getUpperBound - Looks through all the bounds info and |

823 | /// computes the upper bound given the current direction settings |

824 | /// at each level. |

825 | const SCEV *getUpperBound(BoundInfo *Bound) const; |

826 | |

827 | /// exploreDirections - Hierarchically expands the direction vector |

828 | /// search space, combining the directions of discovered dependences |

829 | /// in the DirSet field of Bound. Returns the number of distinct |

830 | /// dependences discovered. If the dependence is disproved, |

831 | /// it will return 0. |

832 | unsigned exploreDirections(unsigned Level, |

833 | CoefficientInfo *A, |

834 | CoefficientInfo *B, |

835 | BoundInfo *Bound, |

836 | const SmallBitVector &Loops, |

837 | unsigned &DepthExpanded, |

838 | const SCEV *Delta) const; |

839 | |

840 | /// testBounds - Returns true iff the current bounds are plausible. |

841 | bool testBounds(unsigned char DirKind, |

842 | unsigned Level, |

843 | BoundInfo *Bound, |

844 | const SCEV *Delta) const; |

845 | |

846 | /// findBoundsALL - Computes the upper and lower bounds for level K |

847 | /// using the * direction. Records them in Bound. |

848 | void findBoundsALL(CoefficientInfo *A, |

849 | CoefficientInfo *B, |

850 | BoundInfo *Bound, |

851 | unsigned K) const; |

852 | |

853 | /// findBoundsLT - Computes the upper and lower bounds for level K |

854 | /// using the < direction. Records them in Bound. |

855 | void findBoundsLT(CoefficientInfo *A, |

856 | CoefficientInfo *B, |

857 | BoundInfo *Bound, |

858 | unsigned K) const; |

859 | |

860 | /// findBoundsGT - Computes the upper and lower bounds for level K |

861 | /// using the > direction. Records them in Bound. |

862 | void findBoundsGT(CoefficientInfo *A, |

863 | CoefficientInfo *B, |

864 | BoundInfo *Bound, |

865 | unsigned K) const; |

866 | |

867 | /// findBoundsEQ - Computes the upper and lower bounds for level K |

868 | /// using the = direction. Records them in Bound. |

869 | void findBoundsEQ(CoefficientInfo *A, |

870 | CoefficientInfo *B, |

871 | BoundInfo *Bound, |

872 | unsigned K) const; |

873 | |

874 | /// intersectConstraints - Updates X with the intersection |

875 | /// of the Constraints X and Y. Returns true if X has changed. |

876 | bool intersectConstraints(Constraint *X, |

877 | const Constraint *Y); |

878 | |

879 | /// propagate - Review the constraints, looking for opportunities |

880 | /// to simplify a subscript pair (Src and Dst). |

881 | /// Return true if some simplification occurs. |

882 | /// If the simplification isn't exact (that is, if it is conservative |

883 | /// in terms of dependence), set consistent to false. |

884 | bool propagate(const SCEV *&Src, |

885 | const SCEV *&Dst, |

886 | SmallBitVector &Loops, |

887 | SmallVectorImpl<Constraint> &Constraints, |

888 | bool &Consistent); |

889 | |

890 | /// propagateDistance - Attempt to propagate a distance |

891 | /// constraint into a subscript pair (Src and Dst). |

892 | /// Return true if some simplification occurs. |

893 | /// If the simplification isn't exact (that is, if it is conservative |

894 | /// in terms of dependence), set consistent to false. |

895 | bool propagateDistance(const SCEV *&Src, |

896 | const SCEV *&Dst, |

897 | Constraint &CurConstraint, |

898 | bool &Consistent); |

899 | |

900 | /// propagatePoint - Attempt to propagate a point |

901 | /// constraint into a subscript pair (Src and Dst). |

902 | /// Return true if some simplification occurs. |

903 | bool propagatePoint(const SCEV *&Src, |

904 | const SCEV *&Dst, |

905 | Constraint &CurConstraint); |

906 | |

907 | /// propagateLine - Attempt to propagate a line |

908 | /// constraint into a subscript pair (Src and Dst). |

909 | /// Return true if some simplification occurs. |

910 | /// If the simplification isn't exact (that is, if it is conservative |

911 | /// in terms of dependence), set consistent to false. |

912 | bool propagateLine(const SCEV *&Src, |

913 | const SCEV *&Dst, |

914 | Constraint &CurConstraint, |

915 | bool &Consistent); |

916 | |

917 | /// findCoefficient - Given a linear SCEV, |

918 | /// return the coefficient corresponding to specified loop. |

919 | /// If there isn't one, return the SCEV constant 0. |

920 | /// For example, given a*i + b*j + c*k, returning the coefficient |

921 | /// corresponding to the j loop would yield b. |

922 | const SCEV *findCoefficient(const SCEV *Expr, |

923 | const Loop *TargetLoop) const; |

924 | |

925 | /// zeroCoefficient - Given a linear SCEV, |

926 | /// return the SCEV given by zeroing out the coefficient |

927 | /// corresponding to the specified loop. |

928 | /// For example, given a*i + b*j + c*k, zeroing the coefficient |

929 | /// corresponding to the j loop would yield a*i + c*k. |

930 | const SCEV *zeroCoefficient(const SCEV *Expr, |

931 | const Loop *TargetLoop) const; |

932 | |

933 | /// addToCoefficient - Given a linear SCEV Expr, |

934 | /// return the SCEV given by adding some Value to the |

935 | /// coefficient corresponding to the specified TargetLoop. |

936 | /// For example, given a*i + b*j + c*k, adding 1 to the coefficient |

937 | /// corresponding to the j loop would yield a*i + (b+1)*j + c*k. |

938 | const SCEV *addToCoefficient(const SCEV *Expr, |

939 | const Loop *TargetLoop, |

940 | const SCEV *Value) const; |

941 | |

942 | /// updateDirection - Update direction vector entry |

943 | /// based on the current constraint. |

944 | void updateDirection(Dependence::DVEntry &Level, |

945 | const Constraint &CurConstraint) const; |

946 | |

947 | /// Given a linear access function, tries to recover subscripts |

948 | /// for each dimension of the array element access. |

949 | bool tryDelinearize(Instruction *Src, Instruction *Dst, |

950 | SmallVectorImpl<Subscript> &Pair); |

951 | |

952 | /// Tries to delinearize \p Src and \p Dst access functions for a fixed size |

953 | /// multi-dimensional array. Calls tryDelinearizeFixedSizeImpl() to |

954 | /// delinearize \p Src and \p Dst separately, |

955 | bool tryDelinearizeFixedSize(Instruction *Src, Instruction *Dst, |

956 | const SCEV *SrcAccessFn, |

957 | const SCEV *DstAccessFn, |

958 | SmallVectorImpl<const SCEV *> &SrcSubscripts, |

959 | SmallVectorImpl<const SCEV *> &DstSubscripts); |

960 | |

961 | /// Tries to delinearize access function for a multi-dimensional array with |

962 | /// symbolic runtime sizes. |

963 | /// Returns true upon success and false otherwise. |

964 | bool tryDelinearizeParametricSize( |

965 | Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, |

966 | const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts, |

967 | SmallVectorImpl<const SCEV *> &DstSubscripts); |

968 | |

969 | /// checkSubscript - Helper function for checkSrcSubscript and |

970 | /// checkDstSubscript to avoid duplicate code |

971 | bool checkSubscript(const SCEV *Expr, const Loop *LoopNest, |

972 | SmallBitVector &Loops, bool IsSrc); |

973 | }; // class DependenceInfo |

974 | |

975 | /// AnalysisPass to compute dependence information in a function |

976 | class DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> { |

977 | public: |

978 | typedef DependenceInfo Result; |

979 | Result run(Function &F, FunctionAnalysisManager &FAM); |

980 | |

981 | private: |

982 | static AnalysisKey Key; |

983 | friend struct AnalysisInfoMixin<DependenceAnalysis>; |

984 | }; // class DependenceAnalysis |

985 | |

986 | /// Printer pass to dump DA results. |

987 | struct DependenceAnalysisPrinterPass |

988 | : public PassInfoMixin<DependenceAnalysisPrinterPass> { |

989 | DependenceAnalysisPrinterPass(raw_ostream &OS, |

990 | bool NormalizeResults = false) |

991 | : OS(OS), NormalizeResults(NormalizeResults) {} |

992 | |

993 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); |

994 | |

995 | private: |

996 | raw_ostream &OS; |

997 | bool NormalizeResults; |

998 | }; // class DependenceAnalysisPrinterPass |

999 | |

1000 | /// Legacy pass manager pass to access dependence information |

1001 | class DependenceAnalysisWrapperPass : public FunctionPass { |

1002 | public: |

1003 | static char ID; // Class identification, replacement for typeinfo |

1004 | DependenceAnalysisWrapperPass(); |

1005 | |

1006 | bool runOnFunction(Function &F) override; |

1007 | void releaseMemory() override; |

1008 | void getAnalysisUsage(AnalysisUsage &) const override; |

1009 | void print(raw_ostream &, const Module * = nullptr) const override; |

1010 | DependenceInfo &getDI() const; |

1011 | |

1012 | private: |

1013 | std::unique_ptr<DependenceInfo> info; |

1014 | }; // class DependenceAnalysisWrapperPass |

1015 | |

1016 | /// createDependenceAnalysisPass - This creates an instance of the |

1017 | /// DependenceAnalysis wrapper pass. |

1018 | FunctionPass *createDependenceAnalysisWrapperPass(); |

1019 | |

1020 | } // namespace llvm |

1021 | |

1022 | #endif |

1023 |