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 22 /// Check if a call is side-effect free and has only constant arguments. 23 /// 24 /// Such calls can be re-generated easily, so we do not need to model them 25 /// as scalar dependences. 26 /// 27 /// @param Call The call to check. 28 bool isConstCall(llvm::CallInst *Call); 29 30 /// Check if some parameters in the affine expression might hide induction 31 /// variables. If this is the case, we will try to delinearize the accesses 32 /// taking into account this information to possibly obtain a memory access 33 /// with more structure. Currently we assume that each parameter that 34 /// comes from a function call might depend on a (virtual) induction variable. 35 /// This covers calls to 'get_global_id' and 'get_local_id' as they commonly 36 /// arise in OpenCL code, while not catching any false-positives in our current 37 /// tests. 38 bool hasIVParams(const llvm::SCEV *Expr); 39 40 /// Find the loops referenced from a SCEV expression. 41 /// 42 /// @param Expr The SCEV expression to scan for loops. 43 /// @param Loops A vector into which the found loops are inserted. 44 void findLoops(const llvm::SCEV *Expr, 45 llvm::SetVector<const llvm::Loop *> &Loops); 46 47 /// Find the values referenced by SCEVUnknowns in a given SCEV 48 /// expression. 49 /// 50 /// @param Expr The SCEV expression to scan for SCEVUnknowns. 51 /// @param SE The ScalarEvolution analysis for this function. 52 /// @param Values A vector into which the found values are inserted. 53 void findValues(const llvm::SCEV *Expr, llvm::ScalarEvolution &SE, 54 llvm::SetVector<llvm::Value *> &Values); 55 56 /// Returns true when the SCEV contains references to instructions within the 57 /// region. 58 /// 59 /// @param Expr The SCEV to analyze. 60 /// @param R The region in which we look for dependences. 61 /// @param Scope Location where the value is needed. 62 /// @param AllowLoops Whether loop recurrences outside the loop that are in the 63 /// region count as dependence. 64 bool hasScalarDepsInsideRegion(const llvm::SCEV *Expr, const llvm::Region *R, 65 llvm::Loop *Scope, bool AllowLoops, 66 const InvariantLoadsSetTy &ILS); 67 bool isAffineExpr(const llvm::Region *R, llvm::Loop *Scope, 68 const llvm::SCEV *Expression, llvm::ScalarEvolution &SE, 69 InvariantLoadsSetTy *ILS = nullptr); 70 71 /// Check if @p V describes an affine constraint in @p R. 72 bool isAffineConstraint(llvm::Value *V, const llvm::Region *R, 73 llvm::Loop *Scope, llvm::ScalarEvolution &SE, 74 ParameterSetTy &Params, bool OrExpr = false); 75 76 ParameterSetTy getParamsInAffineExpr(const llvm::Region *R, llvm::Loop *Scope, 77 const llvm::SCEV *Expression, 78 llvm::ScalarEvolution &SE); 79 80 /// Extract the constant factors from the multiplication @p M. 81 /// 82 /// @param M A potential SCEV multiplication. 83 /// @param SE The ScalarEvolution analysis to create new SCEVs. 84 /// 85 /// @returns The constant factor in @p M and the rest of @p M. 86 std::pair<const llvm::SCEVConstant *, const llvm::SCEV *> 87 extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE); 88 89 /// Try to look through PHI nodes, where some incoming edges come from error 90 /// blocks. 91 /// 92 /// In case a PHI node follows an error block we can assume that the incoming 93 /// value can only come from the node that is not an error block. As a result, 94 /// conditions that seemed non-affine before are now in fact affine. 95 const llvm::SCEV *tryForwardThroughPHI(const llvm::SCEV *Expr, llvm::Region &R, 96 llvm::ScalarEvolution &SE, 97 llvm::LoopInfo &LI, 98 const llvm::DominatorTree &DT); 99 100 /// Return a unique non-error block incoming value for @p PHI if available. 101 /// 102 /// @param R The region to run our code on. 103 /// @param LI The loopinfo tree 104 /// @param DT The dominator tree 105 llvm::Value *getUniqueNonErrorValue(llvm::PHINode *PHI, llvm::Region *R, 106 llvm::LoopInfo &LI, 107 const llvm::DominatorTree &DT); 108 } // namespace polly 109 110 #endif 111