1 | //===--- SCEVValidator.h - Detect Scops -------------------------*- C++ -*-===// |
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 | // Checks if a SCEV expression represents a valid affine expression. |
9 | //===----------------------------------------------------------------------===// |
10 | |
11 | #ifndef POLLY_SCEV_VALIDATOR_H |
12 | #define POLLY_SCEV_VALIDATOR_H |
13 | |
14 | #include "polly/Support/ScopHelper.h" |
15 | |
16 | namespace llvm { |
17 | class SCEVConstant; |
18 | } // namespace llvm |
19 | |
20 | namespace polly { |
21 | class ScopDetection; |
22 | |
23 | /// Find the loops referenced from a SCEV expression. |
24 | /// |
25 | /// @param Expr The SCEV expression to scan for loops. |
26 | /// @param Loops A vector into which the found loops are inserted. |
27 | void findLoops(const llvm::SCEV *Expr, |
28 | llvm::SetVector<const llvm::Loop *> &Loops); |
29 | |
30 | /// Find the values referenced by SCEVUnknowns in a given SCEV |
31 | /// expression. |
32 | /// |
33 | /// @param Expr The SCEV expression to scan for SCEVUnknowns. |
34 | /// @param SE The ScalarEvolution analysis for this function. |
35 | /// @param Values A vector into which the found values are inserted. |
36 | void findValues(const llvm::SCEV *Expr, llvm::ScalarEvolution &SE, |
37 | llvm::SetVector<llvm::Value *> &Values); |
38 | |
39 | /// Returns true when the SCEV contains references to instructions within the |
40 | /// region. |
41 | /// |
42 | /// @param Expr The SCEV to analyze. |
43 | /// @param R The region in which we look for dependences. |
44 | /// @param Scope Location where the value is needed. |
45 | /// @param AllowLoops Whether loop recurrences outside the loop that are in the |
46 | /// region count as dependence. |
47 | bool hasScalarDepsInsideRegion(const llvm::SCEV *Expr, const llvm::Region *R, |
48 | llvm::Loop *Scope, bool AllowLoops, |
49 | const InvariantLoadsSetTy &ILS); |
50 | bool isAffineExpr(const llvm::Region *R, llvm::Loop *Scope, |
51 | const llvm::SCEV *Expression, llvm::ScalarEvolution &SE, |
52 | InvariantLoadsSetTy *ILS = nullptr); |
53 | |
54 | /// Check if @p V describes an affine constraint in @p R. |
55 | bool isAffineConstraint(llvm::Value *V, const llvm::Region *R, |
56 | llvm::Loop *Scope, llvm::ScalarEvolution &SE, |
57 | ParameterSetTy &Params, bool OrExpr = false); |
58 | |
59 | ParameterSetTy getParamsInAffineExpr(const llvm::Region *R, llvm::Loop *Scope, |
60 | const llvm::SCEV *Expression, |
61 | llvm::ScalarEvolution &SE); |
62 | |
63 | /// Extract the constant factors from the multiplication @p M. |
64 | /// |
65 | /// @param M A potential SCEV multiplication. |
66 | /// @param SE The ScalarEvolution analysis to create new SCEVs. |
67 | /// |
68 | /// @returns The constant factor in @p M and the rest of @p M. |
69 | std::pair<const llvm::SCEVConstant *, const llvm::SCEV *> |
70 | (const llvm::SCEV *M, llvm::ScalarEvolution &SE); |
71 | |
72 | /// Try to look through PHI nodes, where some incoming edges come from error |
73 | /// blocks. |
74 | /// |
75 | /// In case a PHI node follows an error block we can assume that the incoming |
76 | /// value can only come from the node that is not an error block. As a result, |
77 | /// conditions that seemed non-affine before are now in fact affine. |
78 | const llvm::SCEV *tryForwardThroughPHI(const llvm::SCEV *Expr, llvm::Region &R, |
79 | llvm::ScalarEvolution &SE, |
80 | ScopDetection *SD); |
81 | |
82 | /// Return a unique non-error block incoming value for @p PHI if available. |
83 | /// |
84 | /// @param R The region to run our code on. |
85 | /// @param SD The ScopDetection |
86 | llvm::Value *getUniqueNonErrorValue(llvm::PHINode *PHI, llvm::Region *R, |
87 | ScopDetection *SD); |
88 | } // namespace polly |
89 | |
90 | #endif |
91 | |