xref: /llvm-project/polly/include/polly/Support/ScopHelper.h (revision 5aafc6d58f3405662902cee006be11e599801b88)

//===------ Support/ScopHelper.h -- 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 LLVM-IR.
//
//===----------------------------------------------------------------------===//

#ifndef POLLY_SUPPORT_IRHELPER_H
#define POLLY_SUPPORT_IRHELPER_H

#include "llvm/ADT/SetVector.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/ValueHandle.h"
#include "isl/isl-noexceptions.h"
#include <optional>

namespace llvm {
class LoopInfo;
class Loop;
class ScalarEvolution;
class SCEV;
class Region;
class Pass;
class DominatorTree;
class RegionInfo;
class RegionNode;
} // namespace llvm

namespace polly {
class Scop;
class ScopStmt;

/// Same as llvm/Analysis/ScalarEvolutionExpressions.h
using LoopToScevMapT = llvm::DenseMap<const llvm::Loop *, const llvm::SCEV *>;

/// Enumeration of assumptions Polly can take.
enum AssumptionKind {
  ALIASING,
  INBOUNDS,
  WRAPPING,
  UNSIGNED,
  PROFITABLE,
  ERRORBLOCK,
  COMPLEXITY,
  INFINITELOOP,
  INVARIANTLOAD,
  DELINEARIZATION,
};

/// Enum to distinguish between assumptions and restrictions.
enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION };

/// Helper struct to remember assumptions.
struct Assumption {
  /// The kind of the assumption (e.g., WRAPPING).
  AssumptionKind Kind;

  /// Flag to distinguish assumptions and restrictions.
  AssumptionSign Sign;

  /// The valid/invalid context if this is an assumption/restriction.
  isl::set Set;

  /// The location that caused this assumption.
  llvm::DebugLoc Loc;

  /// An optional block whose domain can simplify the assumption.
  llvm::BasicBlock *BB;

  // Whether the assumption must be checked at runtime.
  bool RequiresRTC;
};

using RecordedAssumptionsTy = llvm::SmallVector<Assumption, 8>;

/// Record an assumption for later addition to the assumed context.
///
/// This function will add the assumption to the RecordedAssumptions. This
/// collection will be added (@see addAssumption) to the assumed context once
/// all parameters are known and the context is fully built.
///
/// @param RecordedAssumption container which keeps all recorded assumptions.
/// @param Kind The assumption kind describing the underlying cause.
/// @param Set  The relations between parameters that are assumed to hold.
/// @param Loc  The location in the source that caused this assumption.
/// @param Sign Enum to indicate if the assumptions in @p Set are positive
///             (needed/assumptions) or negative (invalid/restrictions).
/// @param BB   The block in which this assumption was taken. If it is
///             set, the domain of that block will be used to simplify the
///             actual assumption in @p Set once it is added. This is useful
///             if the assumption was created prior to the domain.
/// @param RTC  Does the assumption require a runtime check?
void recordAssumption(RecordedAssumptionsTy *RecordedAssumptions,
                      AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc,
                      AssumptionSign Sign, llvm::BasicBlock *BB = nullptr,
                      bool RTC = true);

/// Type to remap values.
using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
                                 llvm::AssertingVH<llvm::Value>>;

/// Type for a set of invariant loads.
using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>;

/// Set type for parameters.
using ParameterSetTy = llvm::SetVector<const llvm::SCEV *>;

/// Set of loops (used to remember loops in non-affine subregions).
using BoxedLoopsSetTy = llvm::SetVector<const llvm::Loop *>;

/// Utility proxy to wrap the common members of LoadInst and StoreInst.
///
/// This works like the LLVM utility class CallSite, ie. it forwards all calls
/// to either a LoadInst, StoreInst, MemIntrinsic or MemTransferInst.
/// It is similar to LLVM's utility classes IntrinsicInst, MemIntrinsic,
/// MemTransferInst, etc. in that it offers a common interface, but does not act
/// as a fake base class.
/// It is similar to StringRef and ArrayRef in that it holds a pointer to the
/// referenced object and should be passed by-value as it is small enough.
///
/// This proxy can either represent a LoadInst instance, a StoreInst instance,
/// a MemIntrinsic instance (memset, memmove, memcpy), a CallInst instance or a
/// nullptr (only creatable using the default constructor); never an Instruction
/// that is neither of the above mentioned. When representing a nullptr, only
/// the following methods are defined:
/// isNull(), isInstruction(), isLoad(), isStore(), ..., isMemTransferInst(),
/// operator bool(), operator!()
///
/// The functions isa, cast, cast_or_null, dyn_cast are modeled to resemble
/// those from llvm/Support/Casting.h. Partial template function specialization
/// is currently not supported in C++ such that those cannot be used directly.
/// (llvm::isa could, but then llvm:cast etc. would not have the expected
/// behavior)
class MemAccInst final {
private:
  llvm::Instruction *I;

public:
  MemAccInst() : I(nullptr) {}
  MemAccInst(const MemAccInst &Inst) : I(Inst.I) {}
  /* implicit */ MemAccInst(llvm::LoadInst &LI) : I(&LI) {}
  /* implicit */ MemAccInst(llvm::LoadInst *LI) : I(LI) {}
  /* implicit */ MemAccInst(llvm::StoreInst &SI) : I(&SI) {}
  /* implicit */ MemAccInst(llvm::StoreInst *SI) : I(SI) {}
  /* implicit */ MemAccInst(llvm::MemIntrinsic *MI) : I(MI) {}
  /* implicit */ MemAccInst(llvm::CallInst *CI) : I(CI) {}
  explicit MemAccInst(llvm::Instruction &I) : I(&I) { assert(isa(I)); }
  explicit MemAccInst(llvm::Instruction *I) : I(I) { assert(isa(I)); }

  static bool isa(const llvm::Value &V) {
    return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
           llvm::isa<llvm::CallInst>(V) || llvm::isa<llvm::MemIntrinsic>(V);
  }
  static bool isa(const llvm::Value *V) {
    return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
           llvm::isa<llvm::CallInst>(V) || llvm::isa<llvm::MemIntrinsic>(V);
  }
  static MemAccInst cast(llvm::Value &V) {
    return MemAccInst(llvm::cast<llvm::Instruction>(V));
  }
  static MemAccInst cast(llvm::Value *V) {
    return MemAccInst(llvm::cast<llvm::Instruction>(V));
  }
  static MemAccInst cast_or_null(llvm::Value &V) {
    return MemAccInst(llvm::cast<llvm::Instruction>(V));
  }
  static MemAccInst cast_or_null(llvm::Value *V) {
    if (!V)
      return MemAccInst();
    return MemAccInst(llvm::cast<llvm::Instruction>(V));
  }
  static MemAccInst dyn_cast(llvm::Value &V) {
    if (isa(V))
      return MemAccInst(llvm::cast<llvm::Instruction>(V));
    return MemAccInst();
  }
  static MemAccInst dyn_cast(llvm::Value *V) {
    assert(V);
    if (isa(V))
      return MemAccInst(llvm::cast<llvm::Instruction>(V));
    return MemAccInst();
  }

  MemAccInst &operator=(const MemAccInst &Inst) {
    I = Inst.I;
    return *this;
  }
  MemAccInst &operator=(llvm::LoadInst &LI) {
    I = &LI;
    return *this;
  }
  MemAccInst &operator=(llvm::LoadInst *LI) {
    I = LI;
    return *this;
  }
  MemAccInst &operator=(llvm::StoreInst &SI) {
    I = &SI;
    return *this;
  }
  MemAccInst &operator=(llvm::StoreInst *SI) {
    I = SI;
    return *this;
  }
  MemAccInst &operator=(llvm::MemIntrinsic &MI) {
    I = &MI;
    return *this;
  }
  MemAccInst &operator=(llvm::MemIntrinsic *MI) {
    I = MI;
    return *this;
  }
  MemAccInst &operator=(llvm::CallInst &CI) {
    I = &CI;
    return *this;
  }
  MemAccInst &operator=(llvm::CallInst *CI) {
    I = CI;
    return *this;
  }

  llvm::Instruction *get() const {
    assert(I && "Unexpected nullptr!");
    return I;
  }
  operator llvm::Instruction *() const { return asInstruction(); }
  llvm::Instruction *operator->() const { return get(); }

  explicit operator bool() const { return isInstruction(); }
  bool operator!() const { return isNull(); }

  llvm::Value *getValueOperand() const {
    if (isLoad())
      return asLoad();
    if (isStore())
      return asStore()->getValueOperand();
    if (isMemIntrinsic())
      return nullptr;
    if (isCallInst())
      return nullptr;
    llvm_unreachable("Operation not supported on nullptr");
  }
  llvm::Value *getPointerOperand() const {
    if (isLoad())
      return asLoad()->getPointerOperand();
    if (isStore())
      return asStore()->getPointerOperand();
    if (isMemIntrinsic())
      return asMemIntrinsic()->getRawDest();
    if (isCallInst())
      return nullptr;
    llvm_unreachable("Operation not supported on nullptr");
  }
  bool isVolatile() const {
    if (isLoad())
      return asLoad()->isVolatile();
    if (isStore())
      return asStore()->isVolatile();
    if (isMemIntrinsic())
      return asMemIntrinsic()->isVolatile();
    if (isCallInst())
      return false;
    llvm_unreachable("Operation not supported on nullptr");
  }
  bool isSimple() const {
    if (isLoad())
      return asLoad()->isSimple();
    if (isStore())
      return asStore()->isSimple();
    if (isMemIntrinsic())
      return !asMemIntrinsic()->isVolatile();
    if (isCallInst())
      return true;
    llvm_unreachable("Operation not supported on nullptr");
  }
  llvm::AtomicOrdering getOrdering() const {
    if (isLoad())
      return asLoad()->getOrdering();
    if (isStore())
      return asStore()->getOrdering();
    if (isMemIntrinsic())
      return llvm::AtomicOrdering::NotAtomic;
    if (isCallInst())
      return llvm::AtomicOrdering::NotAtomic;
    llvm_unreachable("Operation not supported on nullptr");
  }
  bool isUnordered() const {
    if (isLoad())
      return asLoad()->isUnordered();
    if (isStore())
      return asStore()->isUnordered();
    // Copied from the Load/Store implementation of isUnordered:
    if (isMemIntrinsic())
      return !asMemIntrinsic()->isVolatile();
    if (isCallInst())
      return true;
    llvm_unreachable("Operation not supported on nullptr");
  }

  bool isNull() const { return !I; }
  bool isInstruction() const { return I; }

  llvm::Instruction *asInstruction() const { return I; }

  bool isLoad() const { return I && llvm::isa<llvm::LoadInst>(I); }
  bool isStore() const { return I && llvm::isa<llvm::StoreInst>(I); }
  bool isCallInst() const { return I && llvm::isa<llvm::CallInst>(I); }
  bool isMemIntrinsic() const { return I && llvm::isa<llvm::MemIntrinsic>(I); }
  bool isMemSetInst() const { return I && llvm::isa<llvm::MemSetInst>(I); }
  bool isMemTransferInst() const {
    return I && llvm::isa<llvm::MemTransferInst>(I);
  }

  llvm::LoadInst *asLoad() const { return llvm::cast<llvm::LoadInst>(I); }
  llvm::StoreInst *asStore() const { return llvm::cast<llvm::StoreInst>(I); }
  llvm::CallInst *asCallInst() const { return llvm::cast<llvm::CallInst>(I); }
  llvm::MemIntrinsic *asMemIntrinsic() const {
    return llvm::cast<llvm::MemIntrinsic>(I);
  }
  llvm::MemSetInst *asMemSetInst() const {
    return llvm::cast<llvm::MemSetInst>(I);
  }
  llvm::MemTransferInst *asMemTransferInst() const {
    return llvm::cast<llvm::MemTransferInst>(I);
  }
};
} // namespace polly

namespace llvm {
/// Specialize simplify_type for MemAccInst to enable dyn_cast and cast
///        from a MemAccInst object.
template <> struct simplify_type<polly::MemAccInst> {
  typedef Instruction *SimpleType;
  static SimpleType getSimplifiedValue(polly::MemAccInst &I) {
    return I.asInstruction();
  }
};
} // namespace llvm

namespace polly {

/// Simplify the region to have a single unconditional entry edge and a
/// single exit edge.
///
/// Although this function allows DT and RI to be null, regions only work
/// properly if the DominatorTree (for Region::contains) and RegionInfo are kept
/// up-to-date.
///
/// @param R  The region to be simplified
/// @param DT DominatorTree to be updated.
/// @param LI LoopInfo to be updated.
/// @param RI RegionInfo to be updated.
void simplifyRegion(llvm::Region *R, llvm::DominatorTree *DT,
                    llvm::LoopInfo *LI, llvm::RegionInfo *RI);

/// Split the entry block of a function to store the newly inserted
///        allocations outside of all Scops.
///
/// @param EntryBlock The entry block of the current function.
/// @param P          The pass that currently running.
///
void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P);

/// Split the entry block of a function to store the newly inserted
///        allocations outside of all Scops.
///
/// @param DT DominatorTree to be updated.
/// @param LI LoopInfo to be updated.
/// @param RI RegionInfo to be updated.
void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock,
                              llvm::DominatorTree *DT, llvm::LoopInfo *LI,
                              llvm::RegionInfo *RI);

/// Wrapper for SCEVExpander extended to all Polly features.
///
/// This wrapper will internally call the SCEVExpander but also makes sure that
/// all additional features not represented in SCEV (e.g., SDiv/SRem are not
/// black boxes but can be part of the function) will be expanded correctly.
///
/// The parameters are the same as for the creation of a SCEVExpander as well
/// as the call to SCEVExpander::expandCodeFor:
///
/// @param S     The current Scop.
/// @param SE    The Scalar Evolution pass used by @p S.
/// @param GenFn The function to generate code in. Can be the same as @p SE.
/// @param GenSE The Scalar Evolution pass for @p GenFn.
/// @param DL    The module data layout.
/// @param Name  The suffix added to the new instruction names.
/// @param E     The expression for which code is actually generated.
/// @param Ty    The type of the resulting code.
/// @param IP    The insertion point for the new code.
/// @param VMap  A remapping of values used in @p E.
/// @param LoopMap A remapping of loops used in @p E.
/// @param RTCBB The last block of the RTC. Used to insert loop-invariant
///              instructions in rare cases.
llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
                           llvm::Function *GenFn, llvm::ScalarEvolution &GenSE,
                           const llvm::DataLayout &DL, const char *Name,
                           const llvm::SCEV *E, llvm::Type *Ty,
                           llvm::Instruction *IP, ValueMapT *VMap,
                           LoopToScevMapT *LoopMap, llvm::BasicBlock *RTCBB);

/// Return the condition for the terminator @p TI.
///
/// For unconditional branches the "i1 true" condition will be returned.
///
/// @param TI The terminator to get the condition from.
///
/// @return The condition of @p TI and nullptr if none could be extracted.
llvm::Value *getConditionFromTerminator(llvm::Instruction *TI);

/// Get the smallest loop that contains @p S but is not in @p S.
llvm::Loop *getLoopSurroundingScop(Scop &S, llvm::LoopInfo &LI);

/// Get the number of blocks in @p L.
///
/// The number of blocks in a loop are the number of basic blocks actually
/// belonging to the loop, as well as all single basic blocks that the loop
/// exits to and which terminate in an unreachable instruction. We do not
/// allow such basic blocks in the exit of a scop, hence they belong to the
/// scop and represent run-time conditions which we want to model and
/// subsequently speculate away.
///
/// @see getRegionNodeLoop for additional details.
unsigned getNumBlocksInLoop(llvm::Loop *L);

/// Get the number of blocks in @p RN.
unsigned getNumBlocksInRegionNode(llvm::RegionNode *RN);

/// Return the smallest loop surrounding @p RN.
llvm::Loop *getRegionNodeLoop(llvm::RegionNode *RN, llvm::LoopInfo &LI);

/// Check if @p LInst can be hoisted in @p R.
///
/// @param LInst The load to check.
/// @param R     The analyzed region.
/// @param LI    The loop info.
/// @param SE    The scalar evolution analysis.
/// @param DT    The dominator tree of the function.
/// @param KnownInvariantLoads The invariant load set.
///
/// @return True if @p LInst can be hoisted in @p R.
bool isHoistableLoad(llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI,
                     llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT,
                     const InvariantLoadsSetTy &KnownInvariantLoads);

/// Return true iff @p V is an intrinsic that we ignore during code
///        generation.
bool isIgnoredIntrinsic(const llvm::Value *V);

/// Check whether a value an be synthesized by the code generator.
///
/// Some value will be recalculated only from information that is code generated
/// from the polyhedral representation. For such instructions we do not need to
/// ensure that their operands are available during code generation.
///
/// @param V The value to check.
/// @param S The current SCoP.
/// @param SE The scalar evolution database.
/// @param Scope Location where the value would by synthesized.
/// @return If the instruction I can be regenerated from its
///         scalar evolution representation, return true,
///         otherwise return false.
bool canSynthesize(const llvm::Value *V, const Scop &S,
                   llvm::ScalarEvolution *SE, llvm::Loop *Scope);

/// Return the block in which a value is used.
///
/// For normal instructions, this is the instruction's parent block. For PHI
/// nodes, this is the incoming block of that use, because this is where the
/// operand must be defined (i.e. its definition dominates this block).
/// Non-instructions do not use operands at a specific point such that in this
/// case this function returns nullptr.
llvm::BasicBlock *getUseBlock(const llvm::Use &U);

// If the loop is nonaffine/boxed, return the first non-boxed surrounding loop
// for Polly. If the loop is affine, return the loop itself.
//
// @param L             Pointer to the Loop object to analyze.
// @param LI            Reference to the LoopInfo.
// @param BoxedLoops    Set of Boxed Loops we get from the SCoP.
llvm::Loop *getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
                                    const BoxedLoopsSetTy &BoxedLoops);

// If the Basic Block belongs to a loop that is nonaffine/boxed, return the
// first non-boxed surrounding loop for Polly. If the loop is affine, return
// the loop itself.
//
// @param BB            Pointer to the Basic Block to analyze.
// @param LI            Reference to the LoopInfo.
// @param BoxedLoops    Set of Boxed Loops we get from the SCoP.
llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
                                    const BoxedLoopsSetTy &BoxedLoops);

/// Is the given instruction a call to a debug function?
///
/// A debug function can be used to insert output in Polly-optimized code which
/// normally does not allow function calls with side-effects. For instance, a
/// printf can be inserted to check whether a value still has the expected value
/// after Polly generated code:
///
///     int sum = 0;
///     for (int i = 0; i < 16; i+=1) {
///       sum += i;
///       printf("The value of sum at i=%d is %d\n", sum, i);
///     }
bool isDebugCall(llvm::Instruction *Inst);

/// Does the statement contain a call to a debug function?
///
/// Such a statement must not be removed, even if has no side-effects.
bool hasDebugCall(ScopStmt *Stmt);

/// Find a property value in a LoopID.
///
/// Generally, a property MDNode has the format
///
///   !{ !"Name", value }
///
/// In which case the value is returned.
///
/// If the property is just
///
///   !{ !"Name" }
///
/// Then `nullptr` is set to mark the property is existing, but does not carry
/// any value. If the property does not exist, `std::nullopt` is returned.
std::optional<llvm::Metadata *> findMetadataOperand(llvm::MDNode *LoopMD,
                                                    llvm::StringRef Name);

/// Find a boolean property value in a LoopID. The value not being defined is
/// interpreted as a false value.
bool getBooleanLoopAttribute(llvm::MDNode *LoopID, llvm::StringRef Name);

/// Find an integers property value in a LoopID.
std::optional<int> getOptionalIntLoopAttribute(llvm::MDNode *LoopID,
                                               llvm::StringRef Name);

/// Does the loop's LoopID contain a 'llvm.loop.disable_heuristics' property?
///
/// This is equivalent to llvm::hasDisableAllTransformsHint(Loop*), but
/// including the LoopUtils.h header indirectly also declares llvm::MemoryAccess
/// which clashes with polly::MemoryAccess. Declaring this alias here avoid
/// having to include LoopUtils.h in other files.
bool hasDisableAllTransformsHint(llvm::Loop *L);
bool hasDisableAllTransformsHint(llvm::MDNode *LoopID);

/// Represent the attributes of a loop.
struct BandAttr {
  /// LoopID which stores the properties of the loop, such as transformations to
  /// apply and the metadata of followup-loops.
  ///
  /// Cannot be used to identify a loop. Two different loops can have the same
  /// metadata.
  llvm::MDNode *Metadata = nullptr;

  /// The LoopInfo reference for this loop.
  ///
  /// Only loops from the original IR are represented by LoopInfo. Loops that
  /// were generated by Polly are not tracked by LoopInfo.
  llvm::Loop *OriginalLoop = nullptr;
};

/// Get an isl::id representing a loop.
///
/// This takes the ownership of the BandAttr and will be free'd when the
/// returned isl::Id is free'd.
isl::id getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr);

/// Create an isl::id that identifies an original loop.
///
/// Return nullptr if the loop does not need a BandAttr (i.e. has no
/// properties);
///
/// This creates a BandAttr which must be unique per loop and therefore this
/// must not be called multiple times on the same loop as their id would be
/// different.
isl::id createIslLoopAttr(isl::ctx Ctx, llvm::Loop *L);

/// Is @p Id representing a loop?
///
/// Such ids contain a polly::BandAttr as its user pointer.
bool isLoopAttr(const isl::id &Id);

/// Return the BandAttr of a loop's isl::id.
BandAttr *getLoopAttr(const isl::id &Id);

} // namespace polly
#endif