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 extractConstantFactor(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