ScheduleTreeTransform.cpp | Explore in Territory

//===- polly/ScheduleTreeTransform.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
//
//===----------------------------------------------------------------------===//
//
// Make changes to isl's schedule tree data structure.
//
//===----------------------------------------------------------------------===//

#include "polly/ScheduleTreeTransform.h"
#include "polly/Support/GICHelper.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/ScopHelper.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Metadata.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"

#include "polly/Support/PollyDebug.h"
#define DEBUG_TYPE …

usingnamespacepolly;
usingnamespacellvm;

namespace {

/// Copy the band member attributes (coincidence, loop type, isolate ast loop
/// type) from one band to another.
static isl::schedule_node_band
applyBandMemberAttributes(isl::schedule_node_band Target, int TargetIdx,
                          const isl::schedule_node_band &Source,
                          int SourceIdx) { … }

/// Create a new band by copying members from another @p Band. @p IncludeCb
/// decides which band indices are copied to the result.
template <typename CbTy>
static isl::schedule rebuildBand(isl::schedule_node_band OldBand,
                                 isl::schedule Body, CbTy IncludeCb) { … }

/// Rewrite a schedule tree by reconstructing it bottom-up.
///
/// By default, the original schedule tree is reconstructed. To build a
/// different tree, redefine visitor methods in a derived class (CRTP).
///
/// Note that AST build options are not applied; Setting the isolate[] option
/// makes the schedule tree 'anchored' and cannot be modified afterwards. Hence,
/// AST build options must be set after the tree has been constructed.
template <typename Derived, typename... Args>
struct ScheduleTreeRewriter
    : RecursiveScheduleTreeVisitor<Derived, isl::schedule, Args...> { … };

/// Rewrite the schedule tree without any changes. Useful to copy a subtree into
/// a new schedule, discarding everything but.
struct IdentityRewriter : ScheduleTreeRewriter<IdentityRewriter> { … };

/// Rewrite a schedule tree to an equivalent one without extension nodes.
///
/// Each visit method takes two additional arguments:
///
///  * The new domain the node, which is the inherited domain plus any domains
///    added by extension nodes.
///
///  * A map of extension domains of all children is returned; it is required by
///    band nodes to schedule the additional domains at the same position as the
///    extension node would.
///
struct ExtensionNodeRewriter final
    : ScheduleTreeRewriter<ExtensionNodeRewriter, const isl::union_set &,
                           isl::union_map &> { … };

/// Collect all AST build options in any schedule tree band.
///
/// ScheduleTreeRewriter cannot apply the schedule tree options. This class
/// collects these options to apply them later.
struct CollectASTBuildOptions final
    : RecursiveScheduleTreeVisitor<CollectASTBuildOptions> { … };

/// Apply AST build options to the bands in a schedule tree.
///
/// This rewrites a schedule tree with the AST build options applied. We assume
/// that the band nodes are visited in the same order as they were when the
/// build options were collected, typically by CollectASTBuildOptions.
struct ApplyASTBuildOptions final : ScheduleNodeRewriter<ApplyASTBuildOptions> { … };

/// Return whether the schedule contains an extension node.
static bool containsExtensionNode(isl::schedule Schedule) { … }

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

/// Is this node of type mark?
static bool isMark(const isl::schedule_node &Node) { … }

/// Is this node of type band?
static bool isBand(const isl::schedule_node &Node) { … }

#ifndef NDEBUG
/// Is this node a band of a single dimension (i.e. could represent a loop)?
static bool isBandWithSingleLoop(const isl::schedule_node &Node) {
  return isBand(Node) && isl_schedule_node_band_n_member(Node.get()) == 1;
}
#endif

static bool isLeaf(const isl::schedule_node &Node) { … }

/// Create an isl::id representing the output loop after a transformation.
static isl::id createGeneratedLoopAttr(isl::ctx Ctx, MDNode *FollowupLoopMD) { … }

/// A loop consists of a band and an optional marker that wraps it. Return the
/// outermost of the two.

/// That is, either the mark or, if there is not mark, the loop itself. Can
/// start with either the mark or the band.
static isl::schedule_node moveToBandMark(isl::schedule_node BandOrMark) { … }

static isl::schedule_node removeMark(isl::schedule_node MarkOrBand,
                                     BandAttr *&Attr) { … }

/// Remove the mark that wraps a loop. Return the band representing the loop.
static isl::schedule_node removeMark(isl::schedule_node MarkOrBand) { … }

static isl::schedule_node insertMark(isl::schedule_node Band, isl::id Mark) { … }

/// Return the (one-dimensional) set of numbers that are divisible by @p Factor
/// with remainder @p Offset.
///
///  isDivisibleBySet(Ctx, 4, 0) = { [i] : floord(i,4) = 0 }
///  isDivisibleBySet(Ctx, 4, 1) = { [i] : floord(i,4) = 1 }
///
static isl::basic_set isDivisibleBySet(isl::ctx &Ctx, long Factor,
                                       long Offset) { … }

/// Make the last dimension of Set to take values from 0 to VectorWidth - 1.
///
/// @param Set         A set, which should be modified.
/// @param VectorWidth A parameter, which determines the constraint.
static isl::set addExtentConstraints(isl::set Set, int VectorWidth) { … }

/// Collapse perfectly nested bands into a single band.
class BandCollapseRewriter final
    : public ScheduleTreeRewriter<BandCollapseRewriter> { … };

static isl::schedule collapseBands(isl::schedule Sched) { … }

/// Collect sequentially executed bands (or anything else), even if nested in a
/// mark or other nodes whose child is executed just once. If we can
/// successfully fuse the bands, we allow them to be removed.
static void collectPotentiallyFusableBands(
    isl::schedule_node Node,
    SmallVectorImpl<std::pair<isl::schedule_node, isl::schedule_node>>
        &ScheduleBands,
    const isl::schedule_node &DirectChild) { … }

/// Remove dependencies that are resolved by @p PartSched. That is, remove
/// everything that we already know is executed in-order.
static isl::union_map remainingDepsFromPartialSchedule(isl::union_map PartSched,
                                                       isl::union_map Deps) { … }

/// Remove dependencies that are resolved by executing them in the order
/// specified by @p Domains;
static isl::union_map remainigDepsFromSequence(ArrayRef<isl::union_set> Domains,
                                               isl::union_map Deps) { … }

/// Determine whether the outermost loop of to bands can be fused while
/// respecting validity dependencies.
static bool canFuseOutermost(const isl::schedule_node_band &LHS,
                             const isl::schedule_node_band &RHS,
                             const isl::union_map &Deps) { … }

/// Fuse @p LHS and @p RHS if possible while preserving validity dependenvies.
static isl::schedule tryGreedyFuse(isl::schedule_node_band LHS,
                                   isl::schedule_node_band RHS,
                                   const isl::union_map &Deps) { … }

static isl::schedule tryGreedyFuse(isl::schedule_node LHS,
                                   isl::schedule_node RHS,
                                   const isl::union_map &Deps) { … }

/// Fuse all fusable loop top-down in a schedule tree.
///
/// The isl::union_map parameters is the set of validity dependencies that have
/// not been resolved/carried by a parent schedule node.
class GreedyFusionRewriter final
    : public ScheduleTreeRewriter<GreedyFusionRewriter, isl::union_map> { … };

} // namespace

bool polly::isBandMark(const isl::schedule_node &Node) { … }

BandAttr *polly::getBandAttr(isl::schedule_node MarkOrBand) { … }

isl::schedule polly::hoistExtensionNodes(isl::schedule Sched) { … }

isl::schedule polly::applyFullUnroll(isl::schedule_node BandToUnroll) { … }

isl::schedule polly::applyPartialUnroll(isl::schedule_node BandToUnroll,
                                        int Factor) { … }

isl::set polly::getPartialTilePrefixes(isl::set ScheduleRange,
                                       int VectorWidth) { … }

isl::union_set polly::getIsolateOptions(isl::set IsolateDomain,
                                        unsigned OutDimsNum) { … }

isl::union_set polly::getDimOptions(isl::ctx Ctx, const char *Option) { … }

isl::schedule_node polly::tileNode(isl::schedule_node Node,
                                   const char *Identifier,
                                   ArrayRef<int> TileSizes,
                                   int DefaultTileSize) { … }

isl::schedule_node polly::applyRegisterTiling(isl::schedule_node Node,
                                              ArrayRef<int> TileSizes,
                                              int DefaultTileSize) { … }

/// Find statements and sub-loops in (possibly nested) sequences.
static void
collectFissionableStmts(isl::schedule_node Node,
                        SmallVectorImpl<isl::schedule_node> &ScheduleStmts) { … }

isl::schedule polly::applyMaxFission(isl::schedule_node BandToFission) { … }

isl::schedule polly::applyGreedyFusion(isl::schedule Sched,
                                       const isl::union_map &Deps) { … }
llvm/polly/lib/Transform/ScheduleTreeTransform.cpp
