llvm/polly/lib/Transform/FlattenAlgo.cpp

//===------ FlattenAlgo.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
//
//===----------------------------------------------------------------------===//
//
// Main algorithm of the FlattenSchedulePass. This is a separate file to avoid
// the unittest for this requiring linking against LLVM.
//
//===----------------------------------------------------------------------===//

#include "polly/FlattenAlgo.h"
#include "polly/Support/ISLOStream.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/PollyDebug.h"
#include "llvm/Support/Debug.h"
#define DEBUG_TYPE …

usingnamespacepolly;
usingnamespacellvm;

namespace {

/// Whether a dimension of a set is bounded (lower and upper) by a constant,
/// i.e. there are two constants Min and Max, such that every value x of the
/// chosen dimensions is Min <= x <= Max.
bool isDimBoundedByConstant(isl::set Set, unsigned dim) { … }

/// Whether a dimension of a set is (lower and upper) bounded by a constant or
/// parameters, i.e. there are two expressions Min_p and Max_p of the parameters
/// p, such that every value x of the chosen dimensions is
/// Min_p <= x <= Max_p.
bool isDimBoundedByParameter(isl::set Set, unsigned dim) { … }

/// Whether BMap's first out-dimension is not a constant.
bool isVariableDim(const isl::basic_map &BMap) { … }

/// Whether Map's first out dimension is no constant nor piecewise constant.
bool isVariableDim(const isl::map &Map) { … }

/// Whether UMap's first out dimension is no (piecewise) constant.
bool isVariableDim(const isl::union_map &UMap) { … }

/// Compute @p UPwAff - @p Val.
isl::union_pw_aff subtract(isl::union_pw_aff UPwAff, isl::val Val) { … }

/// Compute @UPwAff * @p Val.
isl::union_pw_aff multiply(isl::union_pw_aff UPwAff, isl::val Val) { … }

/// Remove @p n dimensions from @p UMap's range, starting at @p first.
///
/// It is assumed that all maps in the maps have at least the necessary number
/// of out dimensions.
isl::union_map scheduleProjectOut(const isl::union_map &UMap, unsigned first,
                                  unsigned n) { … }

/// Return the @p pos' range dimension, converted to an isl_union_pw_aff.
isl::union_pw_aff scheduleExtractDimAff(isl::union_map UMap, unsigned pos) { … }

/// Flatten a sequence-like first dimension.
///
/// A sequence-like scatter dimension is constant, or at least only small
/// variation, typically the result of ordering a sequence of different
/// statements. An example would be:
///   { Stmt_A[] -> [0, X, ...]; Stmt_B[] -> [1, Y, ...] }
/// to schedule all instances of Stmt_A before any instance of Stmt_B.
///
/// To flatten, first begin with an offset of zero. Then determine the lowest
/// possible value of the dimension, call it "i" [In the example we start at 0].
/// Considering only schedules with that value, consider only instances with
/// that value and determine the extent of the next dimension. Let l_X(i) and
/// u_X(i) its minimum (lower bound) and maximum (upper bound) value. Add them
/// as "Offset + X - l_X(i)" to the new schedule, then add "u_X(i) - l_X(i) + 1"
/// to Offset and remove all i-instances from the old schedule. Repeat with the
/// remaining lowest value i' until there are no instances in the old schedule
/// left.
/// The example schedule would be transformed to:
///   { Stmt_X[] -> [X - l_X, ...]; Stmt_B -> [l_X - u_X + 1 + Y - l_Y, ...] }
isl::union_map tryFlattenSequence(isl::union_map Schedule) { … }

/// Flatten a loop-like first dimension.
///
/// A loop-like dimension is one that depends on a variable (usually a loop's
/// induction variable). Let the input schedule look like this:
///   { Stmt[i] -> [i, X, ...] }
///
/// To flatten, we determine the largest extent of X which may not depend on the
/// actual value of i. Let l_X() the smallest possible value of X and u_X() its
/// largest value. Then, construct a new schedule
///   { Stmt[i] -> [i * (u_X() - l_X() + 1), ...] }
isl::union_map tryFlattenLoop(isl::union_map Schedule) { … }
} // anonymous namespace

isl::union_map polly::flattenSchedule(isl::union_map Schedule) { … }