ScopHelper.cpp | Explore in Territory

//===- ScopHelper.cpp - Some Helper Functions for Scop.  ------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// Small functions that help with Scop and LLVM-IR.
//
//===----------------------------------------------------------------------===//

#include "polly/Support/ScopHelper.h"
#include "polly/Options.h"
#include "polly/ScopInfo.h"
#include "polly/Support/SCEVValidator.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include <optional>

usingnamespacellvm;
usingnamespacepolly;

#define DEBUG_TYPE …

static cl::list<std::string> DebugFunctions(
    "polly-debug-func",
    cl::desc("Allow calls to the specified functions in SCoPs even if their "
             "side-effects are unknown. This can be used to do debug output in "
             "Polly-transformed code."),
    cl::Hidden, cl::CommaSeparated, cl::cat(PollyCategory));

// Ensures that there is just one predecessor to the entry node from outside the
// region.
// The identity of the region entry node is preserved.
static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
                                RegionInfo *RI) { … }

// Ensure that the region has a single block that branches to the exit node.
static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
                               RegionInfo *RI) { … }

void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
                           RegionInfo *RI) { … }

// Split the block into two successive blocks.
//
// Like llvm::SplitBlock, but also preserves RegionInfo
static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
                              DominatorTree *DT, llvm::LoopInfo *LI,
                              RegionInfo *RI) { … }

void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, DominatorTree *DT,
                                     LoopInfo *LI, RegionInfo *RI) { … }

void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) { … }

void polly::recordAssumption(polly::RecordedAssumptionsTy *RecordedAssumptions,
                             polly::AssumptionKind Kind, isl::set Set,
                             DebugLoc Loc, polly::AssumptionSign Sign,
                             BasicBlock *BB, bool RTC) { … }

/// ScopExpander generates IR the the value of a SCEV that represents a value
/// from a SCoP.
///
/// IMPORTANT: There are two ScalarEvolutions at play here. First, the SE that
/// was used to analyze the original SCoP (not actually referenced anywhere
/// here, but passed as argument to make the distinction clear). Second, GenSE
/// which is the SE for the function that the code is emitted into. SE and GenSE
/// may be different when the generated code is to be emitted into an outlined
/// function, e.g. for a parallel loop. That is, each SCEV is to be used only by
/// the SE that "owns" it and ScopExpander handles the translation between them.
/// The SCEVVisitor methods are only to be called on SCEVs of the original SE.
/// Their job is to create a new SCEV for GenSE. The nested SCEVExpander is to
/// be used only with SCEVs belonging to GenSE. Currently SCEVs do not store a
/// reference to the ScalarEvolution they belong to, so a mixup does not
/// immediately cause a crash but certainly is a violation of its interface.
///
/// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
/// instruction but just use it, if it is referenced as a SCEVUnknown. We want
/// however to generate new code if the instruction is in the analyzed region
/// and we generate code outside/in front of that region. Hence, we generate the
/// code for the SDiv/SRem operands in front of the analyzed region and then
/// create a new SDiv/SRem operation there too.
struct ScopExpander final : SCEVVisitor<ScopExpander, const SCEV *> { … };

Value *polly::expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
                            llvm::Function *GenFn, ScalarEvolution &GenSE,
                            const DataLayout &DL, const char *Name,
                            const SCEV *E, Type *Ty, Instruction *IP,
                            ValueMapT *VMap, LoopToScevMapT *LoopMap,
                            BasicBlock *RTCBB) { … }

Value *polly::getConditionFromTerminator(Instruction *TI) { … }

Loop *polly::getLoopSurroundingScop(Scop &S, LoopInfo &LI) { … }

unsigned polly::getNumBlocksInLoop(Loop *L) { … }

unsigned polly::getNumBlocksInRegionNode(RegionNode *RN) { … }

Loop *polly::getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) { … }

static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R,
                            ScalarEvolution &SE) { … }

bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
                            ScalarEvolution &SE, const DominatorTree &DT,
                            const InvariantLoadsSetTy &KnownInvariantLoads) { … }

bool polly::isIgnoredIntrinsic(const Value *V) { … }

bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,
                          Loop *Scope) { … }

llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) { … }

llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
                                           const BoxedLoopsSetTy &BoxedLoops) { … }

llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
                                           llvm::LoopInfo &LI,
                                           const BoxedLoopsSetTy &BoxedLoops) { … }

bool polly::isDebugCall(Instruction *Inst) { … }

static bool hasDebugCall(BasicBlock *BB) { … }

bool polly::hasDebugCall(ScopStmt *Stmt) { … }

/// Find a property in a LoopID.
static MDNode *findNamedMetadataNode(MDNode *LoopMD, StringRef Name) { … }

static std::optional<const MDOperand *> findNamedMetadataArg(MDNode *LoopID,
                                                             StringRef Name) { … }

std::optional<Metadata *> polly::findMetadataOperand(MDNode *LoopMD,
                                                     StringRef Name) { … }

static std::optional<bool> getOptionalBoolLoopAttribute(MDNode *LoopID,
                                                        StringRef Name) { … }

bool polly::getBooleanLoopAttribute(MDNode *LoopID, StringRef Name) { … }

std::optional<int> polly::getOptionalIntLoopAttribute(MDNode *LoopID,
                                                      StringRef Name) { … }

bool polly::hasDisableAllTransformsHint(Loop *L) { … }

bool polly::hasDisableAllTransformsHint(llvm::MDNode *LoopID) { … }

isl::id polly::getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr) { … }

isl::id polly::createIslLoopAttr(isl::ctx Ctx, Loop *L) { … }

bool polly::isLoopAttr(const isl::id &Id) { … }

BandAttr *polly::getLoopAttr(const isl::id &Id) { … }
llvm/polly/lib/Support/ScopHelper.cpp
