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
20namespace polly {
21class 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__.
27typedef 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.
30class SCEVAffinator final : public llvm::SCEVVisitor<SCEVAffinator, PWACtx> {
31public:
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 the object.
54 llvm::LoopInfo *getLI() const { return &LI; }
55
56private:
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 visitVScale(const llvm::SCEVVScale *E);
103 PWACtx visitPtrToIntExpr(const llvm::SCEVPtrToIntExpr *E);
104 PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E);
105 PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E);
106 PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E);
107 PWACtx visitAddExpr(const llvm::SCEVAddExpr *E);
108 PWACtx visitMulExpr(const llvm::SCEVMulExpr *E);
109 PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E);
110 PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E);
111 PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E);
112 PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E);
113 PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E);
114 PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E);
115 PWACtx visitSequentialUMinExpr(const llvm::SCEVSequentialUMinExpr *E);
116 PWACtx visitUnknown(const llvm::SCEVUnknown *E);
117 PWACtx visitSDivInstruction(llvm::Instruction *SDiv);
118 PWACtx visitSRemInstruction(llvm::Instruction *SRem);
119 PWACtx complexityBailout();
120
121 friend struct llvm::SCEVVisitor<SCEVAffinator, PWACtx>;
122};
123} // namespace polly
124
125#endif
126

source code of polly/include/polly/Support/SCEVAffinator.h