llvm/polly/lib/Support/VirtualInstruction.cpp

//===------ VirtualInstruction.cpp ------------------------------*- 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
//
//===----------------------------------------------------------------------===//
//
// Tools for determining which instructions are within a statement and the
// nature of their operands.
//
//===----------------------------------------------------------------------===//

#include "polly/Support/VirtualInstruction.h"

usingnamespacepolly;
usingnamespacellvm;

VirtualUse VirtualUse::create(Scop *S, const Use &U, LoopInfo *LI,
                              bool Virtual) { … }

VirtualUse VirtualUse::create(Scop *S, ScopStmt *UserStmt, Loop *UserScope,
                              Value *Val, bool Virtual) { … }

void VirtualUse::print(raw_ostream &OS, bool Reproducible) const { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void VirtualUse::dump() const {
  print(errs(), false);
  errs() << '\n';
}
#endif

void VirtualInstruction::print(raw_ostream &OS, bool Reproducible) const { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void VirtualInstruction::dump() const {
  print(errs(), false);
  errs() << '\n';
}
#endif

/// Return true if @p Inst cannot be removed, even if it is nowhere referenced.
static bool isRoot(const Instruction *Inst) { … }

/// Return true for MemoryAccesses that cannot be removed because it represents
/// an llvm::Value that is used after the SCoP.
static bool isEscaping(MemoryAccess *MA) { … }

/// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
static void
addInstructionRoots(ScopStmt *Stmt,
                    SmallVectorImpl<VirtualInstruction> &RootInsts) { … }

/// Add non-removable memory accesses in @p Stmt to @p RootInsts.
///
/// @param Local If true, all writes are assumed to escape. markAndSweep
/// algorithms can use this to be applicable to a single ScopStmt only without
/// the risk of removing definitions required by other statements.
///              If false, only writes for SCoP-escaping values are roots.  This
///              is global mode, where such writes must be marked by theirs uses
///              in order to be reachable.
static void addAccessRoots(ScopStmt *Stmt,
                           SmallVectorImpl<MemoryAccess *> &RootAccs,
                           bool Local) { … }

/// Determine all instruction and access roots.
static void addRoots(ScopStmt *Stmt,
                     SmallVectorImpl<VirtualInstruction> &RootInsts,
                     SmallVectorImpl<MemoryAccess *> &RootAccs, bool Local) { … }

/// Mark accesses and instructions as used if they are reachable from a root,
/// walking the operand trees.
///
/// @param S              The SCoP to walk.
/// @param LI             The LoopInfo Analysis.
/// @param RootInsts      List of root instructions.
/// @param RootAccs       List of root accesses.
/// @param UsesInsts[out] Receives all reachable instructions, including the
/// roots.
/// @param UsedAccs[out]  Receives all reachable accesses, including the roots.
/// @param OnlyLocal      If non-nullptr, restricts walking to a single
/// statement.
static void walkReachable(Scop *S, LoopInfo *LI,
                          ArrayRef<VirtualInstruction> RootInsts,
                          ArrayRef<MemoryAccess *> RootAccs,
                          DenseSet<VirtualInstruction> &UsedInsts,
                          DenseSet<MemoryAccess *> &UsedAccs,
                          ScopStmt *OnlyLocal = nullptr) { … }

void polly::markReachable(Scop *S, LoopInfo *LI,
                          DenseSet<VirtualInstruction> &UsedInsts,
                          DenseSet<MemoryAccess *> &UsedAccs,
                          ScopStmt *OnlyLocal) { … }