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 struct SCEVAffinator : 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. getLISCEVAffinator54 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 visitUnknown(const llvm::SCEVUnknown *E); 115 PWACtx visitSDivInstruction(llvm::Instruction *SDiv); 116 PWACtx visitSRemInstruction(llvm::Instruction *SRem); 117 PWACtx complexityBailout(); 118 119 friend struct llvm::SCEVVisitor<SCEVAffinator, PWACtx>; 120 }; 121 } // namespace polly 122 123 #endif 124