polly/Support/SCEVAffinator.h

0001 //===------ polly/SCEVAffinator.h - Create isl expressions from SCEVs -----===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Create a polyhedral description for a SCEV value.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef POLLY_SCEV_AFFINATOR_H
0014 #define POLLY_SCEV_AFFINATOR_H
0015
0016 #include "polly/Support/ScopHelper.h"
0017 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
0018 #include "isl/isl-noexceptions.h"
0019
0020 namespace polly {
0021 class Scop;
0022
0023 /// The result type of the SCEVAffinator.
0024 ///
0025 /// The first element of the pair is the isl representation of the SCEV, the
0026 /// second is the domain under which it is __invalid__.
0027 typedef std::pair<isl::pw_aff, isl::set> PWACtx;
0028
0029 /// Translate a SCEV to an isl::pw_aff and the domain on which it is invalid.
0030 class SCEVAffinator final : public llvm::SCEVVisitor<SCEVAffinator, PWACtx> {
0031 public:
0032   SCEVAffinator(Scop *S, llvm::LoopInfo &LI);
0033
0034   /// Translate a SCEV to an isl::pw_aff.
0035   ///
0036   /// @param E  he expression that is translated.
0037   /// @param BB The block in which @p E is executed.
0038   ///
0039   /// @returns The isl representation of the SCEV @p E in @p Domain.
0040   PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB = nullptr,
0041                   RecordedAssumptionsTy *RecordedAssumptions = nullptr);
0042
0043   /// Take the assumption that @p PWAC is non-negative.
0044   void takeNonNegativeAssumption(
0045       PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions = nullptr);
0046
0047   /// Interpret the PWA in @p PWAC as an unsigned value.
0048   void interpretAsUnsigned(PWACtx &PWAC, unsigned Width);
0049
0050   /// Check an <nsw> AddRec for the loop @p L is cached.
0051   bool hasNSWAddRecForLoop(llvm::Loop *L) const;
0052
0053   /// Return the LoopInfo used by the object.
0054   llvm::LoopInfo *getLI() const { return &LI; }
0055
0056 private:
0057   /// Key to identify cached expressions.
0058   using CacheKey = std::pair<const llvm::SCEV *, llvm::BasicBlock *>;
0059
0060   /// Map to remembered cached expressions.
0061   llvm::DenseMap<CacheKey, PWACtx> CachedExpressions;
0062
0063   Scop *S;
0064   isl::ctx Ctx;
0065   unsigned NumIterators;
0066   llvm::ScalarEvolution &SE;
0067   llvm::LoopInfo &LI;
0068   llvm::BasicBlock *BB;
0069   RecordedAssumptionsTy *RecordedAssumptions = nullptr;
0070
0071   /// Target data for element size computing.
0072   const llvm::DataLayout &TD;
0073
0074   /// Return the loop for the current block if any.
0075   llvm::Loop *getScope();
0076
0077   /// Return a PWACtx for @p PWA that is always valid.
0078   PWACtx getPWACtxFromPWA(isl::pw_aff PWA);
0079
0080   /// Compute the non-wrapping version of @p PWA for type @p ExprType.
0081   ///
0082   /// @param PWA  The piece-wise affine function that might wrap.
0083   /// @param Type The type of the SCEV that was translated to @p PWA.
0084   ///
0085   /// @returns The expr @p PWA modulo the size constraints of @p ExprType.
0086   isl::pw_aff addModuloSemantic(isl::pw_aff PWA, llvm::Type *ExprType) const;
0087
0088   /// If @p Expr might cause an integer wrap record an assumption.
0089   ///
0090   /// @param Expr The SCEV expression that might wrap.
0091   /// @param PWAC The isl representation of @p Expr with the invalid domain.
0092   ///
0093   /// @returns The isl representation @p PWAC with a possibly adjusted domain.
0094   PWACtx checkForWrapping(const llvm::SCEV *Expr, PWACtx PWAC) const;
0095
0096   /// Whether to track the value of this expression precisely, rather than
0097   /// assuming it won't wrap.
0098   bool computeModuloForExpr(const llvm::SCEV *Expr);
0099
0100   PWACtx visit(const llvm::SCEV *E);
0101   PWACtx visitConstant(const llvm::SCEVConstant *E);
0102   PWACtx visitVScale(const llvm::SCEVVScale *E);
0103   PWACtx visitPtrToIntExpr(const llvm::SCEVPtrToIntExpr *E);
0104   PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E);
0105   PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E);
0106   PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E);
0107   PWACtx visitAddExpr(const llvm::SCEVAddExpr *E);
0108   PWACtx visitMulExpr(const llvm::SCEVMulExpr *E);
0109   PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E);
0110   PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E);
0111   PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E);
0112   PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E);
0113   PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E);
0114   PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E);
0115   PWACtx visitSequentialUMinExpr(const llvm::SCEVSequentialUMinExpr *E);
0116   PWACtx visitUnknown(const llvm::SCEVUnknown *E);
0117   PWACtx visitSDivInstruction(llvm::Instruction *SDiv);
0118   PWACtx visitSRemInstruction(llvm::Instruction *SRem);
0119   PWACtx complexityBailout();
0120
0121   friend struct llvm::SCEVVisitor<SCEVAffinator, PWACtx>;
0122 };
0123 } // namespace polly
0124
0125 #endif