llvm/llvm/lib/Transforms/Scalar/LoopDistribute.cpp

//===- LoopDistribute.cpp - Loop Distribution Pass ------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file implements the Loop Distribution Pass.  Its main focus is to
// distribute loops that cannot be vectorized due to dependence cycles.  It
// tries to isolate the offending dependences into a new loop allowing
// vectorization of the remaining parts.
//
// For dependence analysis, the pass uses the LoopVectorizer's
// LoopAccessAnalysis.  Because this analysis presumes no change in the order of
// memory operations, special care is taken to preserve the lexical order of
// these operations.
//
// Similarly to the Vectorizer, the pass also supports loop versioning to
// run-time disambiguate potentially overlapping arrays.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/LoopDistribute.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/LoopVersioning.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <cassert>
#include <functional>
#include <list>
#include <tuple>
#include <utility>

usingnamespacellvm;

#define LDIST_NAME …
#define DEBUG_TYPE …

/// @{
/// Metadata attribute names
static const char *const LLVMLoopDistributeFollowupAll = …;
static const char *const LLVMLoopDistributeFollowupCoincident = …;
static const char *const LLVMLoopDistributeFollowupSequential = …;
static const char *const LLVMLoopDistributeFollowupFallback = …;
/// @}

static cl::opt<bool>
    LDistVerify("loop-distribute-verify", cl::Hidden,
                cl::desc("Turn on DominatorTree and LoopInfo verification "
                         "after Loop Distribution"),
                cl::init(false));

static cl::opt<bool> DistributeNonIfConvertible(
    "loop-distribute-non-if-convertible", cl::Hidden,
    cl::desc("Whether to distribute into a loop that may not be "
             "if-convertible by the loop vectorizer"),
    cl::init(false));

static cl::opt<unsigned> DistributeSCEVCheckThreshold(
    "loop-distribute-scev-check-threshold", cl::init(8), cl::Hidden,
    cl::desc("The maximum number of SCEV checks allowed for Loop "
             "Distribution"));

static cl::opt<unsigned> PragmaDistributeSCEVCheckThreshold(
    "loop-distribute-scev-check-threshold-with-pragma", cl::init(128),
    cl::Hidden,
    cl::desc("The maximum number of SCEV checks allowed for Loop "
             "Distribution for loop marked with #pragma clang loop "
             "distribute(enable)"));

static cl::opt<bool> EnableLoopDistribute(
    "enable-loop-distribute", cl::Hidden,
    cl::desc("Enable the new, experimental LoopDistribution Pass"),
    cl::init(false));

STATISTIC(NumLoopsDistributed, "Number of loops distributed");

namespace {

/// Maintains the set of instructions of the loop for a partition before
/// cloning.  After cloning, it hosts the new loop.
class InstPartition { … };

/// Holds the set of Partitions.  It populates them, merges them and then
/// clones the loops.
class InstPartitionContainer { … };

/// For each memory instruction, this class maintains difference of the
/// number of unsafe dependences that start out from this instruction minus
/// those that end here.
///
/// By traversing the memory instructions in program order and accumulating this
/// number, we know whether any unsafe dependence crosses over a program point.
class MemoryInstructionDependences { … };

/// The actual class performing the per-loop work.
class LoopDistributeForLoop { … };

} // end anonymous namespace

static bool runImpl(Function &F, LoopInfo *LI, DominatorTree *DT,
                    ScalarEvolution *SE, OptimizationRemarkEmitter *ORE,
                    LoopAccessInfoManager &LAIs) { … }

PreservedAnalyses LoopDistributePass::run(Function &F,
                                          FunctionAnalysisManager &AM) { … }