//===- ScopDetection.h - Detect Scops ---------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Detect the maximal Scops of a function.
//
// A static control part (Scop) is a subgraph of the control flow graph (CFG)
// that only has statically known control flow and can therefore be described
// within the polyhedral model.
//
// Every Scop fulfills these restrictions:
//
// * It is a single entry single exit region
//
// * Only affine linear bounds in the loops
//
// Every natural loop in a Scop must have a number of loop iterations that can
// be described as an affine linear function in surrounding loop iterators or
// parameters. (A parameter is a scalar that does not change its value during
// execution of the Scop).
//
// * Only comparisons of affine linear expressions in conditions
//
// * All loops and conditions perfectly nested
//
// The control flow needs to be structured such that it could be written using
// just 'for' and 'if' statements, without the need for any 'goto', 'break' or
// 'continue'.
//
// * Side effect free functions call
//
// Only function calls and intrinsics that do not have side effects are allowed
// (readnone).
//
// The Scop detection finds the largest Scops by checking if the largest
// region is a Scop. If this is not the case, its canonical subregions are
// checked until a region is a Scop. It is now tried to extend this Scop by
// creating a larger non canonical region.
//
//===----------------------------------------------------------------------===//
#ifndef POLLY_SCOPDETECTION_H
#define POLLY_SCOPDETECTION_H
#include "polly/ScopDetectionDiagnostic.h"
#include "polly/Support/ScopHelper.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Pass.h"
#include <set>
namespace polly {
using llvm::AAResults;
using llvm::AliasSetTracker;
using llvm::AnalysisInfoMixin;
using llvm::AnalysisKey;
using llvm::AnalysisUsage;
using llvm::BatchAAResults;
using llvm::BranchInst;
using llvm::CallInst;
using llvm::DenseMap;
using llvm::DominatorTree;
using llvm::Function;
using llvm::FunctionAnalysisManager;
using llvm::FunctionPass;
using llvm::IntrinsicInst;
using llvm::LoopInfo;
using llvm::Module;
using llvm::OptimizationRemarkEmitter;
using llvm::PassInfoMixin;
using llvm::PreservedAnalyses;
using llvm::RegionInfo;
using llvm::ScalarEvolution;
using llvm::SCEVUnknown;
using llvm::SetVector;
using llvm::SmallSetVector;
using llvm::SmallVectorImpl;
using llvm::StringRef;
using llvm::SwitchInst;
using ParamSetType = std::set<const SCEV *>;
// Description of the shape of an array.
struct ArrayShape {
// Base pointer identifying all accesses to this array.
const SCEVUnknown *BasePointer;
// Sizes of each delinearized dimension.
SmallVector<const SCEV *, 4> DelinearizedSizes;
ArrayShape(const SCEVUnknown *B) : BasePointer(B) {}
};
struct MemAcc {
const Instruction *Insn;
// A pointer to the shape description of the array.
std::shared_ptr<ArrayShape> Shape;
// Subscripts computed by delinearization.
SmallVector<const SCEV *, 4> DelinearizedSubscripts;
MemAcc(const Instruction *I, std::shared_ptr<ArrayShape> S)
: Insn(I), Shape(S) {}
};
using MapInsnToMemAcc = std::map<const Instruction *, MemAcc>;
using PairInstSCEV = std::pair<const Instruction *, const SCEV *>;
using AFs = std::vector<PairInstSCEV>;
using BaseToAFs = std::map<const SCEVUnknown *, AFs>;
using BaseToElSize = std::map<const SCEVUnknown *, const SCEV *>;
extern bool PollyTrackFailures;
extern bool PollyDelinearize;
extern bool PollyUseRuntimeAliasChecks;
extern bool PollyProcessUnprofitable;
extern bool PollyInvariantLoadHoisting;
extern bool PollyAllowUnsignedOperations;
extern bool PollyAllowFullFunction;
/// A function attribute which will cause Polly to skip the function
extern StringRef PollySkipFnAttr;
//===----------------------------------------------------------------------===//
/// Pass to detect the maximal static control parts (Scops) of a
/// function.
class ScopDetection {
public:
using RegionSet = SetVector<const Region *>;
// Remember the valid regions
RegionSet ValidRegions;
/// Context variables for SCoP detection.
struct DetectionContext {
Region &CurRegion; // The region to check.
BatchAAResults BAA; // The batched alias analysis results.
AliasSetTracker AST; // The AliasSetTracker to hold the alias information.
bool Verifying; // If we are in the verification phase?
/// If this flag is set, the SCoP must eventually be rejected, even with
/// KeepGoing.
bool IsInvalid = false;
/// Container to remember rejection reasons for this region.
RejectLog Log;
/// Map a base pointer to all access functions accessing it.
///
/// This map is indexed by the base pointer. Each element of the map
/// is a list of memory accesses that reference this base pointer.
BaseToAFs Accesses;
/// The set of base pointers with non-affine accesses.
///
/// This set contains all base pointers and the locations where they are
/// used for memory accesses that can not be detected as affine accesses.
llvm::SetVector<std::pair<const SCEVUnknown *, Loop *>> NonAffineAccesses;
BaseToElSize ElementSize;
/// The region has at least one load instruction.
bool hasLoads = false;
/// The region has at least one store instruction.
bool hasStores = false;
/// Flag to indicate the region has at least one unknown access.
bool HasUnknownAccess = false;
/// The set of non-affine subregions in the region we analyze.
RegionSet NonAffineSubRegionSet;
/// The set of loops contained in non-affine regions.
BoxedLoopsSetTy BoxedLoopsSet;
/// Loads that need to be invariant during execution.
InvariantLoadsSetTy RequiredILS;
/// Map to memory access description for the corresponding LLVM
/// instructions.
MapInsnToMemAcc InsnToMemAcc;
/// Initialize a DetectionContext from scratch.
DetectionContext(Region &R, AAResults &AA, bool Verify)
: CurRegion(R), BAA(AA), AST(BAA), Verifying(Verify), Log(&R) {}
};
/// Helper data structure to collect statistics about loop counts.
struct LoopStats {
int NumLoops;
int MaxDepth;
};
int NextScopID = 0;
int getNextID() { return NextScopID++; }
private:
//===--------------------------------------------------------------------===//
/// Analyses used
//@{
const DominatorTree &DT;
ScalarEvolution &SE;
LoopInfo &LI;
RegionInfo &RI;
AAResults &AA;
//@}
/// Map to remember detection contexts for all regions.
using DetectionContextMapTy =
DenseMap<BBPair, std::unique_ptr<DetectionContext>>;
DetectionContextMapTy DetectionContextMap;
/// Cache for the isErrorBlock function.
DenseMap<std::tuple<const BasicBlock *, const Region *>, bool>
ErrorBlockCache;
/// Remove cached results for @p R.
void removeCachedResults(const Region &R);
/// Remove cached results for the children of @p R recursively.
void removeCachedResultsRecursively(const Region &R);
/// Check if @p S0 and @p S1 do contain multiple possibly aliasing pointers.
///
/// @param S0 A expression to check.
/// @param S1 Another expression to check or nullptr.
/// @param Scope The loop/scope the expressions are checked in.
///
/// @returns True, if multiple possibly aliasing pointers are used in @p S0
/// (and @p S1 if given).
bool involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, Loop *Scope) const;
/// Add the region @p AR as over approximated sub-region in @p Context.
///
/// @param AR The non-affine subregion.
/// @param Context The current detection context.
///
/// @returns True if the subregion can be over approximated, false otherwise.
bool addOverApproximatedRegion(Region *AR, DetectionContext &Context) const;
/// Find for a given base pointer terms that hint towards dimension
/// sizes of a multi-dimensional array.
///
/// @param Context The current detection context.
/// @param BasePointer A base pointer indicating the virtual array we are
/// interested in.
SmallVector<const SCEV *, 4>
getDelinearizationTerms(DetectionContext &Context,
const SCEVUnknown *BasePointer) const;
/// Check if the dimension size of a delinearized array is valid.
///
/// @param Context The current detection context.
/// @param Sizes The sizes of the different array dimensions.
/// @param BasePointer The base pointer we are interested in.
/// @param Scope The location where @p BasePointer is being used.
/// @returns True if one or more array sizes could be derived - meaning: we
/// see this array as multi-dimensional.
bool hasValidArraySizes(DetectionContext &Context,
SmallVectorImpl<const SCEV *> &Sizes,
const SCEVUnknown *BasePointer, Loop *Scope) const;
/// Derive access functions for a given base pointer.
///
/// @param Context The current detection context.
/// @param Sizes The sizes of the different array dimensions.
/// @param BasePointer The base pointer of all the array for which to compute
/// access functions.
/// @param Shape The shape that describes the derived array sizes and
/// which should be filled with newly computed access
/// functions.
/// @returns True if a set of affine access functions could be derived.
bool computeAccessFunctions(DetectionContext &Context,
const SCEVUnknown *BasePointer,
std::shared_ptr<ArrayShape> Shape) const;
/// Check if all accesses to a given BasePointer are affine.
///
/// @param Context The current detection context.
/// @param BasePointer the base pointer we are interested in.
/// @param Scope The location where @p BasePointer is being used.
/// @param True if consistent (multi-dimensional) array accesses could be
/// derived for this array.
bool hasBaseAffineAccesses(DetectionContext &Context,
const SCEVUnknown *BasePointer, Loop *Scope) const;
/// Delinearize all non affine memory accesses and return false when there
/// exists a non affine memory access that cannot be delinearized. Return true
/// when all array accesses are affine after delinearization.
bool hasAffineMemoryAccesses(DetectionContext &Context) const;
/// Try to expand the region R. If R can be expanded return the expanded
/// region, NULL otherwise.
Region *expandRegion(Region &R);
/// Find the Scops in this region tree.
///
/// @param The region tree to scan for scops.
void findScops(Region &R);
/// Check if all basic block in the region are valid.
///
/// @param Context The context of scop detection.
bool allBlocksValid(DetectionContext &Context);
/// Check if a region has sufficient compute instructions.
///
/// This function checks if a region has a non-trivial number of instructions
/// in each loop. This can be used as an indicator whether a loop is worth
/// optimizing.
///
/// @param Context The context of scop detection.
/// @param NumLoops The number of loops in the region.
///
/// @return True if region is has sufficient compute instructions,
/// false otherwise.
bool hasSufficientCompute(DetectionContext &Context,
int NumAffineLoops) const;
/// Check if the unique affine loop might be amendable to distribution.
///
/// This function checks if the number of non-trivial blocks in the unique
/// affine loop in Context.CurRegion is at least two, thus if the loop might
/// be amendable to distribution.
///
/// @param Context The context of scop detection.
///
/// @return True only if the affine loop might be amendable to distributable.
bool hasPossiblyDistributableLoop(DetectionContext &Context) const;
/// Check if a region is profitable to optimize.
///
/// Regions that are unlikely to expose interesting optimization opportunities
/// are called 'unprofitable' and may be skipped during scop detection.
///
/// @param Context The context of scop detection.
///
/// @return True if region is profitable to optimize, false otherwise.
bool isProfitableRegion(DetectionContext &Context) const;
/// Check if a region is a Scop.
///
/// @param Context The context of scop detection.
///
/// @return If we short-circuited early to not waste time on known-invalid
/// SCoPs. Use Context.IsInvalid to determine whether the region is a
/// valid SCoP.
bool isValidRegion(DetectionContext &Context);
/// Check if an intrinsic call can be part of a Scop.
///
/// @param II The intrinsic call instruction to check.
/// @param Context The current detection context.
bool isValidIntrinsicInst(IntrinsicInst &II, DetectionContext &Context) const;
/// Check if a call instruction can be part of a Scop.
///
/// @param CI The call instruction to check.
/// @param Context The current detection context.
bool isValidCallInst(CallInst &CI, DetectionContext &Context) const;
/// Check if the given loads could be invariant and can be hoisted.
///
/// If true is returned the loads are added to the required invariant loads
/// contained in the @p Context.
///
/// @param RequiredILS The loads to check.
/// @param Context The current detection context.
///
/// @return True if all loads can be assumed invariant.
bool onlyValidRequiredInvariantLoads(InvariantLoadsSetTy &RequiredILS,
DetectionContext &Context) const;
/// Check if a value is invariant in the region Reg.
///
/// @param Val Value to check for invariance.
/// @param Reg The region to consider for the invariance of Val.
/// @param Ctx The current detection context.
///
/// @return True if the value represented by Val is invariant in the region
/// identified by Reg.
bool isInvariant(Value &Val, const Region &Reg, DetectionContext &Ctx) const;
/// Check if the memory access caused by @p Inst is valid.
///
/// @param Inst The access instruction.
/// @param AF The access function.
/// @param BP The access base pointer.
/// @param Context The current detection context.
bool isValidAccess(Instruction *Inst, const SCEV *AF, const SCEVUnknown *BP,
DetectionContext &Context) const;
/// Check if a memory access can be part of a Scop.
///
/// @param Inst The instruction accessing the memory.
/// @param Context The context of scop detection.
bool isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const;
/// Check if an instruction can be part of a Scop.
///
/// @param Inst The instruction to check.
/// @param Context The context of scop detection.
bool isValidInstruction(Instruction &Inst, DetectionContext &Context);
/// Check if the switch @p SI with condition @p Condition is valid.
///
/// @param BB The block to check.
/// @param SI The switch to check.
/// @param Condition The switch condition.
/// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch.
/// @param Context The context of scop detection.
bool isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition,
bool IsLoopBranch, DetectionContext &Context) const;
/// Check if the branch @p BI with condition @p Condition is valid.
///
/// @param BB The block to check.
/// @param BI The branch to check.
/// @param Condition The branch condition.
/// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch.
/// @param Context The context of scop detection.
bool isValidBranch(BasicBlock &BB, BranchInst *BI, Value *Condition,
bool IsLoopBranch, DetectionContext &Context);
/// Check if the SCEV @p S is affine in the current @p Context.
///
/// This will also use a heuristic to decide if we want to require loads to be
/// invariant to make the expression affine or if we want to treat is as
/// non-affine.
///
/// @param S The expression to be checked.
/// @param Scope The loop nest in which @p S is used.
/// @param Context The context of scop detection.
bool isAffine(const SCEV *S, Loop *Scope, DetectionContext &Context) const;
/// Check if the control flow in a basic block is valid.
///
/// This function checks if a certain basic block is terminated by a
/// Terminator instruction we can handle or, if this is not the case,
/// registers this basic block as the start of a non-affine region.
///
/// This function optionally allows unreachable statements.
///
/// @param BB The BB to check the control flow.
/// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch.
/// @param AllowUnreachable Allow unreachable statements.
/// @param Context The context of scop detection.
bool isValidCFG(BasicBlock &BB, bool IsLoopBranch, bool AllowUnreachable,
DetectionContext &Context);
/// Is a loop valid with respect to a given region.
///
/// @param L The loop to check.
/// @param Context The context of scop detection.
bool isValidLoop(Loop *L, DetectionContext &Context);
/// Count the number of loops and the maximal loop depth in @p L.
///
/// @param L The loop to check.
/// @param SE The scalar evolution analysis.
/// @param MinProfitableTrips The minimum number of trip counts from which
/// a loop is assumed to be profitable and
/// consequently is counted.
/// returns A tuple of number of loops and their maximal depth.
static ScopDetection::LoopStats
countBeneficialSubLoops(Loop *L, ScalarEvolution &SE,
unsigned MinProfitableTrips);
/// Check if the function @p F is marked as invalid.
///
/// @note An OpenMP subfunction will be marked as invalid.
static bool isValidFunction(Function &F);
/// Can ISL compute the trip count of a loop.
///
/// @param L The loop to check.
/// @param Context The context of scop detection.
///
/// @return True if ISL can compute the trip count of the loop.
bool canUseISLTripCount(Loop *L, DetectionContext &Context);
/// Print the locations of all detected scops.
void printLocations(Function &F);
/// Check if a region is reducible or not.
///
/// @param Region The region to check.
/// @param DbgLoc Parameter to save the location of instruction that
/// causes irregular control flow if the region is irreducible.
///
/// @return True if R is reducible, false otherwise.
bool isReducibleRegion(Region &R, DebugLoc &DbgLoc) const;
/// Track diagnostics for invalid scops.
///
/// @param Context The context of scop detection.
/// @param Assert Throw an assert in verify mode or not.
/// @param Args Argument list that gets passed to the constructor of RR.
template <class RR, typename... Args>
inline bool invalid(DetectionContext &Context, bool Assert,
Args &&...Arguments) const;
public:
ScopDetection(const DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI,
RegionInfo &RI, AAResults &AA, OptimizationRemarkEmitter &ORE);
void detect(Function &F);
/// Get the RegionInfo stored in this pass.
///
/// This was added to give the DOT printer easy access to this information.
RegionInfo *getRI() const { return &RI; }
/// Get the LoopInfo stored in this pass.
LoopInfo *getLI() const { return &LI; }
/// Is the region is the maximum region of a Scop?
///
/// @param R The Region to test if it is maximum.
/// @param Verify Rerun the scop detection to verify SCoP was not invalidated
/// meanwhile. Do not use if the region's DetectionContect is
/// referenced by a Scop that is still to be processed.
///
/// @return Return true if R is the maximum Region in a Scop, false otherwise.
bool isMaxRegionInScop(const Region &R, bool Verify = true);
/// Return the detection context for @p R, nullptr if @p R was invalid.
DetectionContext *getDetectionContext(const Region *R) const;
/// Return the set of rejection causes for @p R.
const RejectLog *lookupRejectionLog(const Region *R) const;
/// Get a message why a region is invalid
///
/// @param R The region for which we get the error message
///
/// @return The error or "" if no error appeared.
std::string regionIsInvalidBecause(const Region *R) const;
/// @name Maximum Region In Scops Iterators
///
/// These iterators iterator over all maximum region in Scops of this
/// function.
//@{
using iterator = RegionSet::iterator;
using const_iterator = RegionSet::const_iterator;
iterator begin() { return ValidRegions.begin(); }
iterator end() { return ValidRegions.end(); }
const_iterator begin() const { return ValidRegions.begin(); }
const_iterator end() const { return ValidRegions.end(); }
//@}
/// Emit rejection remarks for all rejected regions.
///
/// @param F The function to emit remarks for.
void emitMissedRemarks(const Function &F);
/// Mark the function as invalid so we will not extract any scop from
/// the function.
///
/// @param F The function to mark as invalid.
static void markFunctionAsInvalid(Function *F);
/// Verify if all valid Regions in this Function are still valid
/// after some transformations.
void verifyAnalysis();
/// Verify if R is still a valid part of Scop after some transformations.
///
/// @param R The Region to verify.
void verifyRegion(const Region &R);
/// Count the number of loops and the maximal loop depth in @p R.
///
/// @param R The region to check
/// @param SE The scalar evolution analysis.
/// @param MinProfitableTrips The minimum number of trip counts from which
/// a loop is assumed to be profitable and
/// consequently is counted.
/// returns A tuple of number of loops and their maximal depth.
static ScopDetection::LoopStats
countBeneficialLoops(Region *R, ScalarEvolution &SE, LoopInfo &LI,
unsigned MinProfitableTrips);
/// Check if the block is a error block.
///
/// A error block is currently any block that fulfills at least one of
/// the following conditions:
///
/// - It is terminated by an unreachable instruction
/// - It contains a call to a non-pure function that is not immediately
/// dominated by a loop header and that does not dominate the region exit.
/// This is a heuristic to pick only error blocks that are conditionally
/// executed and can be assumed to be not executed at all without the
/// domains being available.
///
/// @param BB The block to check.
/// @param R The analyzed region.
///
/// @return True if the block is a error block, false otherwise.
bool isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R);
private:
/// OptimizationRemarkEmitter object used to emit diagnostic remarks
OptimizationRemarkEmitter &ORE;
};
struct ScopAnalysis : AnalysisInfoMixin<ScopAnalysis> {
static AnalysisKey Key;
using Result = ScopDetection;
ScopAnalysis();
Result run(Function &F, FunctionAnalysisManager &FAM);
};
struct ScopAnalysisPrinterPass final : PassInfoMixin<ScopAnalysisPrinterPass> {
ScopAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
raw_ostream &OS;
};
class ScopDetectionWrapperPass final : public FunctionPass {
std::unique_ptr<ScopDetection> Result;
public:
ScopDetectionWrapperPass();
/// @name FunctionPass interface
///@{
static char ID;
void getAnalysisUsage(AnalysisUsage &AU) const override;
void releaseMemory() override;
bool runOnFunction(Function &F) override;
void print(raw_ostream &OS, const Module *M = nullptr) const override;
///@}
ScopDetection &getSD() const { return *Result; }
};
llvm::Pass *createScopDetectionPrinterLegacyPass(llvm::raw_ostream &OS);
} // namespace polly
namespace llvm {
void initializeScopDetectionWrapperPassPass(llvm::PassRegistry &);
void initializeScopDetectionPrinterLegacyPassPass(llvm::PassRegistry &);
} // namespace llvm
#endif // POLLY_SCOPDETECTION_H