Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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
  125.