llvm/polly/include/polly/ScopInfo.h

//===- polly/ScopInfo.h -----------------------------------------*- 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
//
//===----------------------------------------------------------------------===//
//
// Store the polyhedral model representation of a static control flow region,
// also called SCoP (Static Control Part).
//
// This representation is shared among several tools in the polyhedral
// community, which are e.g. CLooG, Pluto, Loopo, Graphite.
//
//===----------------------------------------------------------------------===//

#ifndef POLLY_SCOPINFO_H
#define POLLY_SCOPINFO_H

#include "polly/ScopDetection.h"
#include "polly/Support/SCEVAffinator.h"
#include "polly/Support/ScopHelper.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Analysis/RegionPass.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "isl/isl-noexceptions.h"
#include <cassert>
#include <cstddef>
#include <forward_list>
#include <optional>

namespace polly {
AnalysisInfoMixin;
ArrayRef;
AssertingVH;
AssumptionCache;
cast;
DataLayout;
DenseMap;
DenseSet;
function_ref;
isa;
iterator_range;
LoadInst;
make_range;
MapVector;
MemIntrinsic;
PassInfoMixin;
PHINode;
RegionNode;
RegionPass;
RGPassManager;
SetVector;
SmallPtrSetImpl;
SmallVector;
SmallVectorImpl;
StringMap;
Type;
Use;
Value;
ValueToValueMap;

class MemoryAccess;

//===---------------------------------------------------------------------===//

extern bool UseInstructionNames;

// The maximal number of basic sets we allow during domain construction to
// be created. More complex scops will result in very high compile time and
// are also unlikely to result in good code.
extern unsigned const MaxDisjunctsInDomain;

/// The different memory kinds used in Polly.
///
/// We distinguish between arrays and various scalar memory objects. We use
/// the term ``array'' to describe memory objects that consist of a set of
/// individual data elements arranged in a multi-dimensional grid. A scalar
/// memory object describes an individual data element and is used to model
/// the definition and uses of llvm::Values.
///
/// The polyhedral model does traditionally not reason about SSA values. To
/// reason about llvm::Values we model them "as if" they were zero-dimensional
/// memory objects, even though they were not actually allocated in (main)
/// memory.  Memory for such objects is only alloca[ed] at CodeGeneration
/// time. To relate the memory slots used during code generation with the
/// llvm::Values they belong to the new names for these corresponding stack
/// slots are derived by appending suffixes (currently ".s2a" and ".phiops")
/// to the name of the original llvm::Value. To describe how def/uses are
/// modeled exactly we use these suffixes here as well.
///
/// There are currently four different kinds of memory objects:
enum class MemoryKind { … };

/// Maps from a loop to the affine function expressing its backedge taken count.
/// The backedge taken count already enough to express iteration domain as we
/// only allow loops with canonical induction variable.
/// A canonical induction variable is:
/// an integer recurrence that starts at 0 and increments by one each time
/// through the loop.
LoopBoundMapType;

AccFuncVector;

/// A class to store information about arrays in the SCoP.
///
/// Objects are accessible via the ScoP, MemoryAccess or the id associated with
/// the MemoryAccess access function.
///
class ScopArrayInfo final { … };

/// Represent memory accesses in statements.
class MemoryAccess final { … };

raw_ostream &operator<<(raw_ostream &OS, MemoryAccess::ReductionType RT);

/// Ordered list type to hold accesses.
MemoryAccessList;

/// Helper structure for invariant memory accesses.
struct InvariantAccess { … };

/// Ordered container type to hold invariant accesses.
InvariantAccessesTy;

/// Type for equivalent invariant accesses and their domain context.
struct InvariantEquivClassTy { … };

/// Type for invariant accesses equivalence classes.
InvariantEquivClassesTy;

/// Statement of the Scop
///
/// A Scop statement represents an instruction in the Scop.
///
/// It is further described by its iteration domain, its schedule and its data
/// accesses.
/// At the moment every statement represents a single basic block of LLVM-IR.
class ScopStmt final { … };

/// Print ScopStmt S to raw_ostream OS.
raw_ostream &operator<<(raw_ostream &OS, const ScopStmt &S);

/// Static Control Part
///
/// A Scop is the polyhedral representation of a control flow region detected
/// by the Scop detection. It is generated by translating the LLVM-IR and
/// abstracting its effects.
///
/// A Scop consists of a set of:
///
///   * A set of statements executed in the Scop.
///
///   * A set of global parameters
///   Those parameters are scalar integer values, which are constant during
///   execution.
///
///   * A context
///   This context contains information about the values the parameters
///   can take and relations between different parameters.
class Scop final { … };

/// Print Scop scop to raw_ostream OS.
raw_ostream &operator<<(raw_ostream &OS, const Scop &scop);

/// The legacy pass manager's analysis pass to compute scop information
///        for a region.
class ScopInfoRegionPass final : public RegionPass { … };

llvm::Pass *createScopInfoPrinterLegacyRegionPass(raw_ostream &OS);

class ScopInfo { … };

struct ScopInfoAnalysis : AnalysisInfoMixin<ScopInfoAnalysis> { … };

struct ScopInfoPrinterPass final : PassInfoMixin<ScopInfoPrinterPass> { … };

//===----------------------------------------------------------------------===//
/// The legacy pass manager's analysis pass to compute scop information
///        for the whole function.
///
/// This pass will maintain a map of the maximal region within a scop to its
/// scop object for all the feasible scops present in a function.
/// This pass is an alternative to the ScopInfoRegionPass in order to avoid a
/// region pass manager.
class ScopInfoWrapperPass final : public FunctionPass { … };

llvm::Pass *createScopInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS);
} // end namespace polly

namespace llvm {
void initializeScopInfoRegionPassPass(PassRegistry &);
void initializeScopInfoPrinterLegacyRegionPassPass(PassRegistry &);
void initializeScopInfoWrapperPassPass(PassRegistry &);
void initializeScopInfoPrinterLegacyFunctionPassPass(PassRegistry &);
} // end namespace llvm

#endif // POLLY_SCOPINFO_H