Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 1 | //===------ polly/SCEVAffinator.h - Create isl expressions from SCEVs -----===// |
| 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 | // Create a polyhedral description for a SCEV value. |
||
| 10 | // |
||
| 11 | //===----------------------------------------------------------------------===// |
||
| 12 | |||
| 13 | #ifndef POLLY_SCEV_AFFINATOR_H |
||
| 14 | #define POLLY_SCEV_AFFINATOR_H |
||
| 15 | |||
| 16 | #include "polly/Support/ScopHelper.h" |
||
| 17 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
||
| 18 | #include "isl/isl-noexceptions.h" |
||
| 19 | |||
| 20 | namespace polly { |
||
| 21 | class Scop; |
||
| 22 | |||
| 23 | /// The result type of the SCEVAffinator. |
||
| 24 | /// |
||
| 25 | /// The first element of the pair is the isl representation of the SCEV, the |
||
| 26 | /// second is the domain under which it is __invalid__. |
||
| 27 | typedef std::pair<isl::pw_aff, isl::set> PWACtx; |
||
| 28 | |||
| 29 | /// Translate a SCEV to an isl::pw_aff and the domain on which it is invalid. |
||
| 30 | class SCEVAffinator final : public llvm::SCEVVisitor<SCEVAffinator, PWACtx> { |
||
| 31 | public: |
||
| 32 | SCEVAffinator(Scop *S, llvm::LoopInfo &LI); |
||
| 33 | |||
| 34 | /// Translate a SCEV to an isl::pw_aff. |
||
| 35 | /// |
||
| 36 | /// @param E he expression that is translated. |
||
| 37 | /// @param BB The block in which @p E is executed. |
||
| 38 | /// |
||
| 39 | /// @returns The isl representation of the SCEV @p E in @p Domain. |
||
| 40 | PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB = nullptr, |
||
| 41 | RecordedAssumptionsTy *RecordedAssumptions = nullptr); |
||
| 42 | |||
| 43 | /// Take the assumption that @p PWAC is non-negative. |
||
| 44 | void takeNonNegativeAssumption( |
||
| 45 | PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions = nullptr); |
||
| 46 | |||
| 47 | /// Interpret the PWA in @p PWAC as an unsigned value. |
||
| 48 | void interpretAsUnsigned(PWACtx &PWAC, unsigned Width); |
||
| 49 | |||
| 50 | /// Check an <nsw> AddRec for the loop @p L is cached. |
||
| 51 | bool hasNSWAddRecForLoop(llvm::Loop *L) const; |
||
| 52 | |||
| 53 | /// Return the LoopInfo used by thi object. |
||
| 54 | llvm::LoopInfo *getLI() const { return &LI; } |
||
| 55 | |||
| 56 | private: |
||
| 57 | /// Key to identify cached expressions. |
||
| 58 | using CacheKey = std::pair<const llvm::SCEV *, llvm::BasicBlock *>; |
||
| 59 | |||
| 60 | /// Map to remembered cached expressions. |
||
| 61 | llvm::DenseMap<CacheKey, PWACtx> CachedExpressions; |
||
| 62 | |||
| 63 | Scop *S; |
||
| 64 | isl::ctx Ctx; |
||
| 65 | unsigned NumIterators; |
||
| 66 | llvm::ScalarEvolution &SE; |
||
| 67 | llvm::LoopInfo &LI; |
||
| 68 | llvm::BasicBlock *BB; |
||
| 69 | RecordedAssumptionsTy *RecordedAssumptions = nullptr; |
||
| 70 | |||
| 71 | /// Target data for element size computing. |
||
| 72 | const llvm::DataLayout &TD; |
||
| 73 | |||
| 74 | /// Return the loop for the current block if any. |
||
| 75 | llvm::Loop *getScope(); |
||
| 76 | |||
| 77 | /// Return a PWACtx for @p PWA that is always valid. |
||
| 78 | PWACtx getPWACtxFromPWA(isl::pw_aff PWA); |
||
| 79 | |||
| 80 | /// Compute the non-wrapping version of @p PWA for type @p ExprType. |
||
| 81 | /// |
||
| 82 | /// @param PWA The piece-wise affine function that might wrap. |
||
| 83 | /// @param Type The type of the SCEV that was translated to @p PWA. |
||
| 84 | /// |
||
| 85 | /// @returns The expr @p PWA modulo the size constraints of @p ExprType. |
||
| 86 | isl::pw_aff addModuloSemantic(isl::pw_aff PWA, llvm::Type *ExprType) const; |
||
| 87 | |||
| 88 | /// If @p Expr might cause an integer wrap record an assumption. |
||
| 89 | /// |
||
| 90 | /// @param Expr The SCEV expression that might wrap. |
||
| 91 | /// @param PWAC The isl representation of @p Expr with the invalid domain. |
||
| 92 | /// |
||
| 93 | /// @returns The isl representation @p PWAC with a possibly adjusted domain. |
||
| 94 | PWACtx checkForWrapping(const llvm::SCEV *Expr, PWACtx PWAC) const; |
||
| 95 | |||
| 96 | /// Whether to track the value of this expression precisely, rather than |
||
| 97 | /// assuming it won't wrap. |
||
| 98 | bool computeModuloForExpr(const llvm::SCEV *Expr); |
||
| 99 | |||
| 100 | PWACtx visit(const llvm::SCEV *E); |
||
| 101 | PWACtx visitConstant(const llvm::SCEVConstant *E); |
||
| 102 | PWACtx visitPtrToIntExpr(const llvm::SCEVPtrToIntExpr *E); |
||
| 103 | PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E); |
||
| 104 | PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E); |
||
| 105 | PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E); |
||
| 106 | PWACtx visitAddExpr(const llvm::SCEVAddExpr *E); |
||
| 107 | PWACtx visitMulExpr(const llvm::SCEVMulExpr *E); |
||
| 108 | PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E); |
||
| 109 | PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E); |
||
| 110 | PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E); |
||
| 111 | PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E); |
||
| 112 | PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E); |
||
| 113 | PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E); |
||
| 114 | PWACtx visitSequentialUMinExpr(const llvm::SCEVSequentialUMinExpr *E); |
||
| 115 | PWACtx visitUnknown(const llvm::SCEVUnknown *E); |
||
| 116 | PWACtx visitSDivInstruction(llvm::Instruction *SDiv); |
||
| 117 | PWACtx visitSRemInstruction(llvm::Instruction *SRem); |
||
| 118 | PWACtx complexityBailout(); |
||
| 119 | |||
| 120 | friend struct llvm::SCEVVisitor<SCEVAffinator, PWACtx>; |
||
| 121 | }; |
||
| 122 | } // namespace polly |
||
| 123 | |||
| 124 | #endif |